Series-parallel graph

Series-parallel graph --- параллельно-последовательный граф.

Series-parallel graphs are recursively defined as:

(1) A one-vertex graph with a loop is series-paralel.

(2) Subdividing an edge of a series-parallel graph [math]\displaystyle{ G }[/math] with a new vertex gives a series-parallel graph (the series operation).

(3) Creating a parallel edge for a non-loop edge of a series-parallel graph (the parallel operation).

(4) There are no further series-parallel graphs.

Note that these graphs can have loops and multiple edges. Since series-parallel graphs are the graphs which contain no subgraphs homeomorphic to [math]\displaystyle{ K_{4} }[/math], the outerplanar graphs are series-parallel graphs.

See also

• Transitive series-parallel graph.