Home

Introduction

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, such as graph depth first search (DFS), lowpoint, and planar embedding face traversal.

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

• Debian Linux (doc)
• Open Graph Drawing Framework (doc)
• Boost (bibl)
• LinKnot (bibl),
• Magma (bibl),
• Nauty (doc),
• Sage (bibl),
• Hagberg's Python Wrapper, and
• Gleich's MatLab Wrapper.

Software Component and Source Code Overview

Wrapper Application

The planarity.exe application provides menu and command-line methods to simplify accessing the functionality of the planarity-related algorithms offered by the APIs of this source code project. It includes the following components and files:

• Main Program & Menu User Interface (planarity.c, planarity.h)
• Command-Line Interface (planarityCommandLine.c)
• Randomly Generate and Process Graphs (planarityRandomGraphs.c)
• Read and Process a Specific Graph (planritySpecificGraph.c)
• Low-Level Application Utilities & Definitions (planarityUtils.c, platformTime.h)

Core Planarity Algorithms

The core edge addition planarity algorithm is provided by the following components and source files:

• Planar & Outerplanar Graph Embedders (graphEmbed.c)
• Planarity & Outerplanarity Obstruction Detection and Isolation (graphNonplanar.c, graphIsolator.c, graphOuterplanarObstructions.c)
• Planarity Preprocessing Algorithms (graphDFSUtils.c)

Ancillary Algorithm Modules

There are a number of supporting data structures and methods, as follows:

• Public API Declarations, Graph Data Structure Definitions, Basic Graph Operations (graph.h, graphStructures.h, appconst.h, graphUtils.c)
• Graph Reading/Writing (graphIO.c)
• List Collection Data Structure (listcoll.c, listcoll.h)
• Stack Data Structure (stack.c, stack.h)
• Check Correctness of Core and Extension Algorithm Outputs (graphTests.c)
• Extension Mechanism (graphExtensions.c, graphExtensions.h, graphExtensions.private.h, graphFunctionTable.h)

Extension Algorithms

The core planarity algorithm can be augmented to solve several planarity-related problems. Based on the extension mechanism, the following additional algorithms are implemented:

• Planar Graph Drawing (graphDrawPlanar_Extensions.c, graphDrawPlanar.c, graphDrawPlanar.h, graphDrawPlanar.private.h)
• Search for Subgraphs Homeomorphic to K_{2,3} (graphK23Search_Extensions.c, graphK23Search.c, graphK23Search.h, graphK23Search.private.h)
• Search for Subgraphs Homeomorphic to K_{4} (graphK4Search_Extensions.c, graphK4Search.c, graphK4Search.h, graphK23Search.private.h)
• Search for Subgraphs Homeomorphic to K_{3,3} (graphK33Search_Extensions.c, graphK33Search.c, graphK33Search.h, graphK33Search.private.h)