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.