<p>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.</p>
<p>It was shown [<a href="https://doi.org/10.1016/j.ipl.2017.10.008" rel="noreferrer">1</a>, 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.</p>
<p><a href="https://doi.org/10.1016/j.ipl.2017.10.008" rel="noreferrer">1</a> Pietro Cenciarelli, Daniele Gorla, Ivano Salvo: <a href="https://doi.org/10.1016/j.ipl.2017.10.008" rel="noreferrer">Inefficiencies in network models: A graph-theoretic perspective</a>. Information Processing Letters 131 (2018) 44–50.</p>

CC BY-SA 4.0
2020-10-02T08:24:40.683Z
2020-10-02T08:31:18.840Z
2020-10-02T08:31:18.840Z
Christian Komusiewicz
<p>According to this <a href="https://en.wikipedia.org/wiki/Series-parallel_graph" rel="noreferrer">Wikipage</a> series-parallel graphs are characterized like this:</p>
<blockquote>
<p>2-connected series-parallel graphs are characterized by having no subgraph homeomorphic to <span class="math-container">$K_4$</span>.</p>
</blockquote>
<p>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 (<span class="math-container">$K_4$</span> minus one edge plus specific orientation):</p>
<p><a href="https://i.sstatic.net/7IM36.png" rel="noreferrer"><img src="https://i.sstatic.net/7IM36.png" alt="Subgraph" /></a></p>
<p>Is it correct? Is it proven anywhere?</p>

<graph-theory>
Series-parallel DAG characterization
HEKTO
# Series-parallel DAG characterization

(Asked by: username_0 on 2020-09-29)

According to this [Wikipage](https://en.wikipedia.org/wiki/Series-parallel_graph) 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):

[![Subgraph](https://i.sstatic.net/7IM36.png)](https://i.sstatic.net/7IM36.png)

Is it correct? Is it proven anywhere?

**Tags:** graph-theory


---

## 1 answers

### Answer by username_1 on 2020-10-02. Score: 7 | Accepted answer

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](https://doi.org/10.1016/j.ipl.2017.10.008), 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](https://doi.org/10.1016/j.ipl.2017.10.008) Pietro Cenciarelli, Daniele Gorla, Ivano Salvo: [Inefficiencies in network models: A graph-theoretic perspective](https://doi.org/10.1016/j.ipl.2017.10.008). Information Processing Letters 131 (2018) 44–50.


---

