Cross-series-parallel digraphs (Q1983112)

By restricting to the class of series-parallel graphs or digraphs, many hard problems can be shown to be solvable in polynomial time. The series-parallel digraphs come in two versions, the vertex version and the edge version. In fact, both versions can be transferred into each other by the reverse line digraph construction. This is possible because series-parallel digraphs are a subclass of the so-called CBC-digraphs, where CBC-digraphs are precisely the class of digraphs for which line digraphs exist. Series-parallel digraphs have already been generalized in various directions. Some of the generalizations control the structure of certain emerging induced subdigraphs called N's. In the present paper, the authors concentrate on another generalization of directed series-parallel digraphs, where the structure of induced N's is much less controlled, the so-called cross-series-parallel digraphs. It is shown that this class of directed digraphs can efficiently be recognized by a decomposition approach, and this decomposition is not unique and does not lead to a tree but a planar graph.