Generalization
The generalized series-parallel graphs (GSP-graphs) are an extension of the SPGs with the same algorithmic efficiency for the mentioned problems. The class of GSP-graphs include the classes of SP-graphs and outerplanar graphs.
GSP graphs may be specified by the Definition 2 augmented with the third operation of deletion of a dangling vertex (vertex of degree 1). Alternatively, Definition 1 may be augmented with the following operation.
- The source merge S = M(X,Y) of two TTGs X and Y is a TTG created from the disjoint union of graphs X and Y by merging the source of X with the source of Y. The source and sink of X become the source and sink of P respectively.
An SPQR tree is a tree structure that can be defined for an arbitrary 2-vertex-connected graph. It has S nodes that are analogous to the series composition operations in series-parallel graphs, P nodes that are analogous to the parallel composition operations in series-parallel graphs, and R nodes that do not correspond to series-parallel composition operations. A 2-connected graph is series-parallel if and only if there are no R nodes in its SPQR tree.
Read more about this topic: Series-parallel Graph