Graph recognition

Series-parallel graphs

A series-parallel graph is a graph which can be obtained from a single edge by recursive application of two production rules: (1) Replacing any edge by parallel edges with the same end nodes as the original edge, and (2) subdividing an edge. It is possible to extend this concept to digraphs and mixed graphs.

Recognition of series-parallel (di)graphs means to revert the production process and to represent it by a so-called decomposition tree. The tree is used for the combinatorial embedding (ordering of the incidence list) and by the drawing method.

It is pretty obvious that series-parallel graphs are planar, even upward-planar. And embedding a series-parallel graph exposes plane incidence orders. When series-parallel graphs are drawn, visibility representations result:

[See API]

Directed acyclic graphs (DAGs)

A DAG is a digraph not containing directed cycles or, equivalently, which has a topologic ordering (a node enumeration such that for every eligible arc, the start node has a smaller number than the end node). And by the second characterization, DAGs can be recognized in linear time.

The importance of DAGs is that minimum and maximum length paths can be also computed in linear time, irrespective of the edge length signs: Predecessor arcs and distance labels are just assigned in the topologic node order.

[See API]

Chordal graphs

A chord with respect to to a cycle is an arc connecting two non-adjacent nodes of the cycle. A non-triangle cycle without any chords is called a hole. A graph is chordal if it does not have any holes. A graph is co-chordal if the complementary graph is chordal.

As a positive characterization, chordal graphs are the graphs which admit a so-called perfect elimination order. The first node in this order is simplicial, that is, its neighbors form a clique. After deleting the minimal node from the graph, the same holds for the remaining graph, the induced order and the follow-up minimal node.

Both chordal and co-chordal graph can be recognized in linear time by using a technique called lexicographic breadth first search. The recognition takes some further steps which also admit a linear time implementation, but the actual code is O(m log(m)) due to a universal edge sort.

It is remarkable that the co-chordality check runs without explicit generation of the complementary graph.

[See API]

Return to main page