Home

This source code project provides a library for implementing graph algorithms as well as implementations of several planarity-related graph algorithms. The origin of this project was to provide reference implementations for Edge Addition Planarity-Related Algorithms. This project includes implementations of:

• the core Edge Addition Planarity Algorithm, which is now the fastest and simplest linear-time method for planar graph embedding and planarity obstruction isolation (i.e., Kuratowski subgraph isolation)
• a method for drawing planar graphs using visibility representations (as well as an ascii art renderer)
• an outerplanar graph embedder and outerplanar obstruction isolator
• a number of subgraph homeomorphism search algorithms
• low-level methods, such as for vertex, adjacency list, and edge iteration, visitation tracking, adding/deleting edges, and mixed directed and undirected edges
• utility methods, such as for copying and duplicating graphs, performing depth first search (DFS), computing lowpoints, determining biconnected components, and traversing planar embedding faces.
• graph I/O methods, such as for adjacency list and matrix formats, G6, and GraphML.

There has been successful technology transfer into other projects of this project's code or algorithms, including:

• Debian Linux (doc), openSUSE (pkg, bld), Ubuntu, and related (see repology)
• Alpine, ALT, Arch, Fedora, FreeBSD, Manjaro, and MSYS2 (see repology)
• Gentoo Linux (doc)
• SageMath (bibl, code)
• Open Graph Drawing Framework (doc)
• Boost (bibl)
• The Digraphs Project (code subdir(s))
• Magma (bibl)
• LinKnot: Knot Theory by Computer (see p. 7, 38 in the book)
• Nauty and Traces (doc, former site)
• Gleich's MatLab-BGL Package uses Boost to make the Edge Addition Planarity Algorithm available to MatLab developers
• The RBGL Boost Interface makes a version of the Edge Addition Planarity Algorithm available to R developers
• The Graph Analysis and Drawing (Grad) Library makes the Edge Addition Planarity Algorithm available to Java developers (see especially this Java source file)
• The Graph Planarity Testing project makes the Edge Addition Planarity Algorithm available to C# developers
• The Planarity Python Package originated by Aric Hagberg is now a repo in the Graph Algorithms organization. This package makes the entire Edge Addition Planarity Suite's graph library is available to Python developers

For more information, please see the sections below:

1. Project Overview

2. Dev Setup

3. Test Support