Options
Cross–series–parallel digraphs
Publikationstyp
Journal Article
Date Issued
2021-11-15
Sprache
English
Author(s)
Institut
TORE-URI
Journal
Volume
33
Start Page
57
End Page
65
Citation
Discrete Applied Mathematics 303: 57-65 (2021-11-15)
Publisher DOI
Scopus ID
Series–parallel directed graphs have been generalized in various directions. Some of these generalizations control the structure of certain emerging induced subdigraphs called N's. They allow an efficient recognition by decomposition trees. We introduce another class of directed acyclic digraphs generalizing series–parallel directed graphs with less structure of induced N's. We show that they still can be efficiently recognized by a decomposition approach. In contrast, however, to the other mentioned generalization this decomposition is not unique and does not lead to a tree but a planar graph.
Subjects
Church–Rosser property
Decomposition
Directed graph
Series–parallel