Series-parallel graph
In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.
Definition and terminology
In this context, the term graph means multigraph.
There are several ways to define series-parallel graphs. The following definition basically follows the one used by David Eppstein.[1]
A two-terminal graph (TTG) is a graph with two distinguished vertices, s and t called source and sink, respectively.
The parallel composition Pc = Pc(X,Y) of two TTGs X and Y is a TTG created from the disjoint union of graphs X and Y by merging the sources of X and Y to create the source of Pc and merging the sinks of X and Y to create the sink of Pc.
The series composition Sc = Sc(X,Y) of two TTGs X and Y is a TTG created from the disjoint union of graphs X and Y by merging the sink of X with the source of Y. The source of X becomes the source of Sc and the sink of Y becomes the sink of Sc.
A two-terminal series-parallel graph (TTSPG) is a graph that may be constructed by a sequence of series and parallel compositions starting from a set of copies of a single-edge graph K2 with assigned terminals.
Definition 1. Finally, a graph is called series-parallel (SP-graph), if it is a TTSPG when some two of its vertices are regarded as source and sink.
In a similar way one may define series-parallel digraphs, constructed from copies of single-arc graphs, with arcs directed from the source to the sink.
Alternative definition
The following definition specifies the same class of graphs.[2]
Definition 2. A graph is an SP-graph, if it may be turned into K2 by a sequence of the following operations:
- Replacement of a pair of parallel edges with a single edge that connects their common endpoints
- Replacement of a pair of edges incident to a vertex of degree 2 other than s or t with a single edge.
Properties
Every series-parallel graph has treewidth at most 2 and branchwidth at most 2.[3] Indeed, a graph has treewidth at most 2 if and only if it has branchwidth at most 2, if and only if every biconnected component is a series-parallel graph.[4][5] The maximal series-parallel graphs, graphs to which no additional edges can be added without destroying their series-parallel structure, are exactly the 2-trees.
2-connected series-parallel graphs are characterised by having no subgraph homeomorphic to K4.[3]
Series parallel graphs may also be characterized by their ear decompositions.[1]
Computational complexity
SP-graphs may be recognized in linear time[6] and their series-parallel decomposition may be constructed in linear time as well.
Besides being a model of certain types of electric networks, these graphs are of interest in computational complexity theory, because a number of standard graph problems are solvable in linear time on SP-graphs,[7] including finding of the maximum matching, maximum independent set, minimum dominating set and Hamiltonian completion. Some of these problems are NP-complete for general graphs. The solution capitalizes on the fact that if the answers for one of these problems are known for two SP-graphs, then one can quickly find the answer for their series and parallel compositions.
Generalization
The generalized series-parallel graphs (GSP-graphs) are an extension of the SP-graphs[8] 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 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, which are analogous to the series composition operations in series-parallel graphs, P-nodes, which are analogous to the parallel composition operations in series-parallel graphs, and R-nodes, which 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.
References
- Eppstein, David (1992). "Parallel recognition of series-parallel graphs" (PDF). Information and Computation. 98 (1): 41–55. doi:10.1016/0890-5401(92)90041-D.
- Duffin, R. J. (1965). "Topology of Series-Parallel Networks". Journal of Mathematical Analysis and Applications. 10 (2): 303–313. doi:10.1016/0022-247X(65)90125-3.
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999). Graph classes: a survey. SIAM Monographs on Discrete Mathematics. and Applications. 3. Philadelphia, PA: Society for Industrial and Applied Mathematics. pp. 172–174. ISBN 978-0-898714-32-6. Zbl 0919.05001.
- Bodlaender, H. (1998). "A partial k-arboretum of graphs with bounded treewidth". Theoretical Computer Science. 209 (1–2): 1–45. doi:10.1016/S0304-3975(97)00228-4.
- Hall, Rhiannon; Oxley, James; Semple, Charles; Whittle, Geoff (2002). "On matroids of branch-width three". Journal of Combinatorial Theory, Series B. 86 (1): 148–171. doi:10.1006/jctb.2002.2120.
- Valdes, Jacobo; Tarjan, Robert E.; Lawler, Eugene L. (1982). "The recognition of series parallel digraphs". SIAM Journal on Computing. 11 (2): 289–313. doi:10.1137/0211023.
- Takamizawa, K.; Nishizeki, T.; Saito, N. (1982). "Linear-time computability of combinatorial problems on series-parallel graphs". Journal of the ACM. 29 (3): 623–641. doi:10.1145/322326.322328.
- Korneyenko, N. M. (1994). "Combinatorial algorithms on a class of graphs". Discrete Applied Mathematics. 54 (2–3): 215–217. doi:10.1016/0166-218X(94)90022-1. Translated from Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, pp. 109–111 (in Russian)