Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
According to this Wikipage series-parallel graphs are characterized like this:
2-connected series-parallel graphs are characterized by having no subgraph homeomorphic to $K_4$.
I couldn't find a similar characterization for series-parallel directed acyclic graphs (DAGs), however I think that the prohibited subgraph in this case can be a little simpler ($K_4$ minus one edge plus specific orientation):
Is it correct? Is it proven anywhere?
The two-connected series-parallel DAGs are also called 2-terminal series-parallel graphs. The graph in the figure is also known as Wheatstone graph and is known as the example graph for demonstrating Braess' paradox in algorithmic game theory.
It was shown [1, Theorem 5.3] that a DAG is 2-terminal series-parallel if and only if it does not contain a subgraph that is homeomorphic to the Wheatstone graph.
1 Pietro Cenciarelli, Daniele Gorla, Ivano Salvo: Inefficiencies in network models: A graph-theoretic perspective. Information Processing Letters 131 (2018) 44–50.
