Series-parallel order

A class of partial order. A partially ordered set has a series-parallel order if it can be constructed recursively from the one-point ordered set using the operations $+$ and $*$ defined on orders as follows. Let $P_1,{<}$ and $P_2,{<}$ be disjoint ordered sets. Each of $P_1 + P_2$ and $P_1 * P_2$ has as underlying set the disjoint union $P_1 \sqcup P_2$ and an order $\prec$ where in each case $\prec$ restricted to $P_1$ and to $P_2$ gives the original order. In $P_1 + P_2$ all pairs $p_1,p_2$ with $P_1 \in P_1$ and $p_2 \in P_2$ are incomparable (parallel); in $P_1 * P_2$, then all such pairs have $p_1 \prec p_2$ (series). We note that $+$ is commutative but $*$ is not.

Each operation is an example of the ordered sum, the operation $+$ corresponding to the trivial order on the indices $\{1,2\}$ and $*$ corresponding to the order $1<2$.

Series-parallel graphs are characterised by being "N-free": having no subset $\{a,b,c,d\}$ with only the comparisons $a \prec b$, $a \prec d$, $c \prec d$.

Series-parallel graphs have dimension at most $2$.

The comparability graphs of series-parallel orders are the cographs.

References[edit]

• Andreas Brandstädt, Van Bang Le; Jeremy P. Spinrad, "Graph classes: a survey". SIAM Monographs on Discrete Mathematics and Applications 3. Society for Industrial and Applied Mathematics (1999) ISBN 978-0-898714-32-6 Zbl 0919.05001
• Caspard, Nathalie; Leclerc, Bruno; Monjardet, Bernard Finite ordered sets. Concepts, results and uses Encyclopedia of Mathematics and its Applications 144 Cambridge University Press (2012) ISBN 978-1-107-01369-8 Zbl 1238.06001