Skip to content

1. Project Overview

Jump to bottom
John M. Boyer edited this page Jun 4, 2026 · 14 revisions

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:

  • The Main Program and Help Messages (planarity.c/.h, planarityHelp.c)
  • Command-Line and Menu-Driven Interfaces (planarityCommandLine.c, planarityMenu.c)
  • Randomly Generate and Process Graphs (planarityRandomGraphs.c)
  • Read and Process a Specific Graph (planritySpecificGraph.c)
  • Test All Graphs in a Given File using a Specified Algorithm (planarityTestAllGraphs.c)
  • Transform between Supported Graph File Formats (planarityTransformGraph.c)
  • Low-Level Application Utilities & Definitions (planarityUtils.c, platformTime.h)

These wrapper application source code files appear in the planarityApp directory, and the source code in these files calls upon graph processing APIs appearing in the Graph Library described next.

The Graph Library

The graph processing API is provided by source code files appearing in the graphLib directory. These APIs include the ability to create and store in-memory graph data structures, to read and write graphs to and from the memory data structures, and to perform various low-level operations as well as high-level algorithms on the in-memory graph data structures. These capabilities are organized into subdirectories described in the sections below.

At the root source code level, as a sibling of the graphLib subdirectory, there is a header file named graphLib.h that consumers of this project's Graph Library can include in their own applications (in place of using the Planarity wrapper application). This header file is just a helper stub that redirects to the graphLib.h header file of the same name within the graphLib subdirectory.

The public GraphLib API consists of all definitions and methods that can be reached by including graphLib.h. While there are additional header files that end with "private.h", these are not reachable by including graphLib.h, are excluded by make install, and should not be used except when developing a code contribution to the GraphLib API.

Basic Graph Representation and I/O

The baseline for graph data structure representation and processing is provided by source code files that are directly within the graphLib directory, including::

  • Public API Declarations, Graph Data Structure Definitions, Basic Graph Operations (graphLib.c/.h, graph.c/.h/.private.h)
  • Depth-First Search, Sorting Vertices by Depth-First Index, Least Ancestor and Lowpoint (graphDFSUtils.c/.h/.private.h)

The source code files in graphLib/io are for reading into and writing graphs out from the in-memory graph data structure:

  • The public read/write APIs and support for several formats (graphIO.c/.h)
  • Source code dedicated to supporting the G6 file format (g6-read-iterator.c/.h, g6-write-iterator.c/.h, g6-api-utilities.c)
  • Data structures and operations to hide the difference between in-memory and file-based I/O (strOrFile.c/.h, strbuf.c/.h)

Extensibility Support for the Graph Library

The Graph Library supports the ability to "subclass" the baseline Graph data structure to extend it with additional data and "virtual" function overloads. This subclassing extension system is defined in graphLib/extensionSystem:

  • The ability to extend the graph, vertex, and edge levels of the in-memory graph (graphExtensions.c/.h/.private.h)
  • The virtual function table (graphFunctionTable.h)

The extension system is used by algorithm implementations in the graphLib/planarityRelated and graphLib/homeomorphSearch subdirectories.

Core Planarity-Related Algorithms

The original purpose for developing the Graph Library was to provide the in-memory data structures and I/O support routines needed to provide a reference implementation of the Edge Addition Planarity Algorithm. This functionality is provided in graphLib/planarityRelated as follows:

  • Planar Graph Embedder Methods (graphEmbed.c, graphPlanarity.h/.private.h, graphPlanarity_Extensions.c)
  • Outerplanar Graph Embedder Methods (graphEmbed.c, graphOuterplanarity.h/.private.h, graphOuterplanarity_Extensions.c)
  • Planarity & Outerplanarity Obstruction Detection and Isolation (graphNonplanar.c, graphIsolator.c, graphOuterplanarObstructions.c)
  • Check Correctness of Embedding and Obstruction Isolation Algorithm Outputs (graphTests.c)
  • Planar Graph Drawing (graphDrawPlanar_Extensions.c, graphDrawPlanar.c/.h/.private.h)

Homeomorphic Subgraph Search Algorithms

The core Edge Addition Planarity Algorithm and Outerplanarity Algorithm can be augmented to solve homeomorphic subgraph search algorithms based on the obstructions to planarity and outerplanarity. These are implemented with the extension system and appear in the graphLib/homeomorphSearch subdirectory:

  • Search for a Subgraph Homeomorphic to K2,3 (graphK23Search_Extensions.c, graphK23Search.c and .h, graphK23Search.private.h)
  • Search for a Subgraph Homeomorphic to K4 (graphK4Search_Extensions.c, graphK4Search.c and .h, graphK4Search.private.h)
  • Search for a Subgraph Homeomorphic to K3,3 (graphK33Search_Extensions.c, graphK33Search.c and .h, graphK33Search.private.h)

Low-Level Utilities of the Graph Library

In the graphLib/lowLevelUtils directory, there are some public and mostly package-private support data structures, macros, and functions as follows:

  • Public helper functions (appconst.h, apiutils.c/.h)
  • A package-private List Collection data structure (listcoll.c/.h) that provides storage and manipulation for any number of lists of objects indicated by integer indices. Typical usage: Optimized storage and processing of lists of vertices, each list containing different vertices.
  • A package-private integer Stack data structure (stack.c/.h) that is typically allocated to the maximum size needed and which provides fast operations needed by depth-first search and planarity-related graph algorithms.
  • Other package-private definitions (apiutils.private.h)

Introduction to the Graph API

Creating and Reading or Building a Graph

To begin working with graphs, create an instance of the graph data structure using gp_New(), like this:

#include "graphLib.h"
...
graphP theGraph = gp_New();

As an optional step, you can configure the newly allocated graph structure with a maximum number of edges higher than the default of 3N edges, where N is the number of vertices. If you know a higher number of edges edges M that you would like to start with, and then pass that value to gp_EnsureEdgeCapacity(). It is more efficient to set a higher edge capacity before using gp_EnsureVertexCapacity() or gp_Read() because the capacity is changed in constant time without having to resize the internal edge storage.

The last step in getting a graph ready to process is to either use gp_Read() to read vertices and edges from a file or use gp_EnsureVertexCapacity() to make an empty graph with N vertices and then use invocations of methods such as gp_AddEdge() or gp_DynamicAddEdge() to add edges. For an example of using gp_Read(), see the implementation of SpecificGraph() in planaritySpecificGraph.c. For an example of using gp_AddEdge(), see the implementation of gp_CreateRandomGraph() in graph.c.

Vertex Array Iteration

After a graph has been created and then built or read from a file, your program will have a reference to the in-memory graph instance with a variable, such as theGraph variable above. The code sample below shows the preferred method for iterating through the vertices sequentially to do some processing. As a simple example of vertex array iteration, this code sums across all vertices all of the outbound edges leading away from all vertices. This excludes edges that are inbound only and includes directed edges that lead away from a vertex as well as undirected edges that are inbound and outbound:

sumOutDegrees = 0;
for (v = gp_LowerBoundVertices(theGraph); v < gp_UpperBoundVertices(theGraph); ++v) 
{
    sumOutDegrees += gp_GetVertexOutDegree(theGraph, v);
}

The main vertex array V in the graph data structure is created to contain 2N vertex records, N for representing the vertices of the graph, and an additional N vertex records to represent virtual vertices. Virtual vertices are used to create extra copies of vertices for algorithm-specific purposes. For example, the planarity-related algorithms in this project use virtual vertices to help represent cut vertices in the multiple biconnected components that contain them. The iteration pattern above loops through the first N non-virtual vertices of the graph. The iteration pattern for processing virtual vertices is the same, except you would instead use gp_LowerBoundVirtualVertices() and gp_UpperBoundVirtualVertices(). For an easy code sample that shows both iteration loops, please see _ClearVertexVisitedFlags() in graph.c.

Adjacency List Iteration and Edge Array Iteration

Each edge of a graph is represented by a pair of edge records stored consecutively in edge array E in the graph data structure. By using array indices as pointers, the edge records are arranged into doubly linked lists called adjacency lists, which are are associated with vertices in a manner described below. Since an edge (v, w) has endpoints v and w, the adjacency list of vertex v contains an edge record indicating vertex w as a neighbor, and the adjacency list of w contains the twin edge record that indicates the index of vertex v as a neighbor.

To process all edges incident to a vertex v, a loop can be used to iterate v's adjacency list. To continue the example in the prior example, we can take a look at the loop construct in the implementation of gp_GetVertexOutDegree() that is in graph.c:

degree = 0;
e = gp_GetFirstEdge(theGraph, v);
while (gp_IsEdge(theGraph, e))
{
     if (gp_GetDirection(theGraph, e) != EDGEFLAG_DIRECTION_INONLY)
         degree++;
     e = gp_GetNextEdge(theGraph, e);
}

Each vertex record contains pointers to (indices of) the first and last edge records in its adjacency list. The loop initialization uses gp_GetFirstEdge() to obtain the first edge record pointing to a neighbor of a vertex v. The while loop body is performed if the index e indicates a valid edge record in the edge array, and the end of the loop body uses gp_GetNextEdge() to enable iteration through each edge record in the adjacency list of v. The method returns NIL as the next edge record after the last in the adjacency list of v, at which point the loop terminates. The method gp_GetDirection() is used to ensure that each edge adds to the outward degree count if it is either undirected or directed outward from v, but not if it is an inward edge that only leads into v from a neighbor vertex w.

To process all edges (pairs of edge records) in the edge array, the following iteration pattern should be used:

for (e = gp_LowerBoundEdges(theGraph); e < gp_UpperBoundEdges(theGraph); e+=2)
{
    if (gp_EdgeInUse(theGraph, e)) {
        // Process edge e and its twin returned by gp_GetTwin(theGraph, e)
    }
}

It is also possible to iterate through all edges by iterating through all vertices and then traversing their adjacency lists. However, when it is easier to express edge processing by iterating over the edge array instead, then analogous to the vertex array, gp_LowerBoundEdges() and gp_UpperBoundEdges() are used. However, it is also necessary to skip edge records that have not been deleted using gp_EdgeInUse(). Also, since an edge is represented by two edge records, it is common for the loop body to process both at the same time and then increment the loop variable by 2, as shown above.

Undirected versus Directed Graphs

The current graph API supports input, representation, and output of both undirected and directed graphs. Digraph input is supported by gp_Read() in the adjacency list format. When reading the adjacency list of a vertex v, the occurrence of a vertex index w is interpreted as an outward directed edge from v to w, so v's adjacency list receives an edge record containing w's index that is flagged with EDGEFLAG_DIRECTION_OUTONLY, and w's adjacency list receives an edge record containing v's index that is flagged with EDGEFLAG_DIRECTION_INONLY. If, in a later reading of the adjacency list of w, there appears the index of v, then the direction flags on both edge records are cleared to indicate that the edge is undirected. Therefore, in terms of representation, it is legitimate to traverse an edge from v to w if the edge record containing w has no direction flag setting or if it is set to EDGEFLAG_DIRECTION_OUTONLY, but not if the direction flag is set to EDGEFLAG_DIRECTION_INONLY. Digraph output is supported by gp_Write() in the adjacency list format in a manner consistent with edge traversal. When outputting the adjacency list for a vertex v, the method gp_Write() will output w for an edge record containing w if the edge record has no direction flag set or if the flag is set to EDGEFLAG_DIRECTION_OUTONLY.

The Planarity-Related Algorithm Pattern

The high-level pattern for planarity-related algorithms is as follows:

  • Create an empty graph data structure with gp_New(),
  • Create the right graph subclass using an "extend with" method (such as gp_ExtendWith_Planarity() or gp_ExtendWith_K33Search())
  • Read a graph with gp_Read() or build it with gp_EnsureVertexCapacity() and gp_AddEdge() as described in the section above,
  • Call gp_Embed() with the embedding flags for the desired planarity-related algorithm (see below),
    • Process the OK (embeddable) or NONEMBEDDABLE return result
    • Optional: Process and output the modified graph with gp_SortVertices() and gp_Write()
  • Release the graph data structure with gp_Free(), or reuse it by calling gp_ResetGraphStorage()

The gp_Embed() method processes an input graph as if it is undirected because the decision about whether edges will cross in an embedding is unrelated to their direction. Although it is possible to read or build a digraph, the implementation of gp_Embed() simply ignores the edge direction flags. This includes underlying planarity pre-processing methods such as gp_DepthFirstSearch(). When writing other graph applications that are not planarity-related, some utility methods such as gp_DepthFirstSearch() are public because they may be still useful, but in these cases the application author may need to write their own similar implementation if alternative behavior is required. For example, depth first search on an undirected graph is provided by gp_DepthFirstSearch(), but a similar alternative implementation would be required for depth first search on a digraph.

A set of embedding flags is available to help control the specific planarity-related algorithm that gp_Embed() executes. See GetEmbedFlags() in planarityUtils.c for various flags that you can currently use, including the following:

  • EMBEDFLAGS_PLANAR for planarity testing, embedding, and obstruction isolation;
  • EMBEDFLAGS_OUTERPLANAR for outerplanarity testing, embedding, and obstruction isolation;
  • EMBEDFLAGS_DRAWPLANAR to execute an extension function set that enables gp_Embed() to calculate a visibility representation and a textual rendering of a planar graph;
  • EMBEDFLAGS_SEARCHFORK23 to execute an extension function set that enables gp_Embed() to determine if a graph contains a subgraph homeomorphic to K2,3 and, if so, returns it;
  • EMBEDFLAGS_SEARCHFORK4 to enable an extension that enables gp_Embed() to determine if a graph contains a subgraph homeomorphic to K4 and, if so, returns it; and
  • EMBEDFLAGS_SEARCHFORK33 to execute an extension function set that enables gp_Embed() to determine if a graph contains a subgraph homeomorphic to K3,3 and, if so, returns it.

The method SpecificGraph() in planaritySpecificGraph.c expresses a variation of this high-level pattern with a few notable differences:

  • After a graph is read from a file with gp_Read(), it is duplicated using gp_DupGraph() so that the graph modifications made by gp_Embed() can be tested for correctness;
  • The modifications to the graph made by gp_Embed() are tested for correctness using gp_TestEmbedResultIntegrity(). The tests performed are specific to the algorithm executed and the embedding result.

Developing Your Own Graph Algorithms in C or Python

Many of the methods used to develop the planarity-related algorithms are also useful in developing your own graph algorithms. The most important files to examine are graph.h, graphIO.h, and graphDFSUtils.h for additional methods that enable you to:

  • Get and set visited and marked flags on vertices and edges
  • Iterate through vertices, edges, and the adjacency list of any vertex
  • Get the degree, in-degree, and out-degree of vertices
  • Get and set the direction of any edge
  • Get the edge type set by depth-first search (tree edge versus back edge)
  • Get the depth-first index, parent, least ancestor, and lowpoint of any vertex
  • Add, delete, and contract edges
  • Identify and de-identify (restore) vertices
  • Copy, duplicate, read, and write graphs

Finally, to use this Graph Library to develop a graph algorithm or application in Python, see the Python Planarity Repository.

Clone this wiki locally