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:
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.
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.
Return to main page