View source for 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 of a partially ordered set|dimension]] at most $2$.

The [[comparability graph]]s of series-parallel orders are the [[cograph]]s.

==References==
* 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}}