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 is the reference implementation for the 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). This project includes implementations of:

• the core Edge Addition Planarity Algorithm (combinatorial planar graph embedder and planarity obstruction isolator)
• 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
• several useful low-level methods, including graph DFS, lowpoint, and planar embedding face traversal.

There has been successful technology transfer of this planarity algorithm into other projects, including:

• Debian Linux (doc)
• Boost (bibl)
• LinKnot (bibl),
• Magma (bibl),
• Nauty (doc),
• Sage (bibl), and
• Hagberg's Python Wrapper.