Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Series–parallel graph
open-in-new
<h2 id="definition-and-terminology">Definition and terminology</h2> <p>In this context, the term graph means <a href="/facts/Multigraph/udmS0Cp0">multigraph</a>. </p><p>There are several ways to define series–parallel graphs. </p> <h3>First definition</h3> <p>The following definition basically follows the one used by <a href="/facts/David_Eppstein/hIjTU6nC">David Eppstein</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> </p><p>A two-terminal graph (TTG) is a graph with two distinguished vertices, <i>s</i> and <i>t</i> called <i>source</i> and <i>sink</i>, respectively. </p><p>The parallel composition <i>Pc = Pc(X,Y)</i> of two TTGs <i>X</i> and <i>Y</i> is a TTG created from the <a href="/facts/Disjoint_union_of_graphs/J0eE3mpB">disjoint union of graphs</a> <i>X</i> and <i>Y</i> by <a href="/facts/Vertex_merging/5po6Cfac">merging</a> the sources of <i>X</i> and <i>Y</i> to create the source of <i>Pc</i> and merging the sinks of <i>X</i> and <i>Y</i> to create the sink of <i>Pc</i>. </p><p>The series composition <i>Sc = Sc(X,Y)</i> of two TTGs <i>X</i> and <i>Y</i> is a TTG created from the disjoint union of graphs <i>X</i> and <i>Y</i> by merging the sink of <i>X</i> with the source of <i>Y</i>. The source of <i>X</i> becomes the source of <i>Sc</i> and the sink of <i>Y</i> becomes the sink of <i>Sc</i>. </p><p>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 <i><a href="/facts/Complete_graph/AYD6hUqI">K</a>2</i> with assigned terminals. </p><p><i>Definition 1</i>. 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. </p><p>In a similar way one may define series–parallel <a href="/facts/Digraph_(mathematics)/YBdfQ0um">digraphs</a>, constructed from copies of single-arc graphs, with arcs directed from the source to the sink. </p> <h3>Second definition</h3> <p>The following definition specifies the same class of graphs.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p><i>Definition 2</i>. A graph is an SP-graph, if it may be turned into <i><a href="/facts/Complete_graph/AYD6hUqI">K</a>2</i> by a sequence of the following operations: </p> <ul><li>Replacement of a pair of parallel edges with a single edge that connects their common endpoints</li> <li>Replacement of a pair of edges incident to a vertex of degree 2 other than <i>s</i> or <i>t</i> with a single edge.</li></ul> <h2 id="properties">Properties</h2> <p>Every series–parallel graph has <a href="/facts/Treewidth/uoITxzRJ">treewidth</a> at most 2 and <a href="/facts/Branchwidth/Cc7HEATJ">branchwidth</a> at most 2.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> Indeed, a graph has treewidth at most 2 if and only if it has branchwidth at most 2, if and only if every <a href="/facts/Biconnected_component/Y4221AkA">biconnected component</a> is a series–parallel graph.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> The <a href="/facts/Maximal_element/7FCC9qAW">maximal</a> series–parallel graphs, graphs to which no additional edges can be added without destroying their series–parallel structure, are exactly the <a href="/facts/K-tree/qgdXYe5r">2-trees</a>. </p><p>2-connected series–parallel graphs are characterised by having no subgraph <a href="/facts/Homeomorphism_(graph_theory)/WbFo1mNW">homeomorphic</a> to K4.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p><p>Series parallel graphs may also be characterized by their <a href="/facts/Ear_decomposition/k4m5lI09">ear decompositions</a>.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <h2 id="computational-complexity">Computational complexity</h2> <p>SP-graphs may be recognized in linear time<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> and their series–parallel decomposition may be constructed in linear time as well. </p><p>Besides being a model of certain types of electric networks, these graphs are of interest in <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, because a number of standard graph problems are solvable in linear time on SP-graphs,<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> including finding of the <a href="/facts/Maximum_matching/oKaChmBt">maximum matching</a>, <a href="/facts/Maximum_independent_set/ksu46kdz">maximum independent set</a>, <a href="/facts/Minimum_dominating_set/3xX4kSnP">minimum dominating set</a> and <a href="/facts/Hamiltonian_completion/E63XC6ex">Hamiltonian completion</a>. Some of these problems are <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> 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. </p> <h2 id="generalization">Generalization</h2> <p>The generalized series–parallel graphs (GSP-graphs) are an extension of the SP-graphs<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> with the same <a href="/facts/Algorithmic_efficiency/VutjvPTd">algorithmic efficiency</a> for the mentioned problems. The class of GSP-graphs include the classes of SP-graphs and <a href="/facts/Outerplanar_graph/FrAgUpcV">outerplanar graphs</a>. </p><p>GSP graphs may be specified by <i>Definition 2</i> augmented with the third operation of <a href="/facts/Vertex_deletion/5po6Cfac">deletion</a> of a dangling vertex (vertex of degree 1). Alternatively, <i>Definition 1</i> may be augmented with the following operation. </p> <ul><li>The source merge <i>S = M(X,Y)</i> of two TTGs <i>X</i> and <i>Y</i> is a TTG created from the disjoint union of graphs <i>X</i> and <i>Y</i> by merging the source of <i>X</i> with the source of <i>Y</i>. The source and sink of <i>X</i> become the source and sink of <i>S</i> respectively.</li></ul> <p>An <a href="/facts/SPQR_tree/M5caazhq">SPQR tree</a> is a tree structure that can be defined for an arbitrary <a href="/facts/Vertex_connectivity/EST9uf8W">2-vertex-connected graph</a>. 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. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Threshold_graph/qMhSrdUd">Threshold graph</a></li> <li><a href="/facts/Cograph/c3lYz8fV">Cograph</a></li> <li><a href="/facts/Hanner_polytope/muTkDlfA">Hanner polytope</a></li> <li><a href="/facts/Series-parallel_partial_order/X8VP9aRR">Series-parallel partial order</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. <a href="https://doi.org/10.1016%2F0022-247X%2865%2990125-3" target="_blank">https://doi.org/10.1016%2F0022-247X%2865%2990125-3</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999). Graph classes: a survey. SIAM Monographs on Discrete Mathematics. and Applications. Vol. 3. Philadelphia, PA: Society for Industrial and Applied Mathematics. pp. 172–174. ISBN 978-0-898714-32-6. Zbl 0919.05001. <a href="978-0-898714-32-6" target="_blank">978-0-898714-32-6</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>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. hdl:1874/18312. <a href="/wiki/Hans_L._Bodlaender" target="_blank">/wiki/Hans_L._Bodlaender</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>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. <a href="https://doi.org/10.1006%2Fjctb.2002.2120" target="_blank">https://doi.org/10.1006%2Fjctb.2002.2120</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy P. (1999). Graph classes: a survey. SIAM Monographs on Discrete Mathematics. and Applications. Vol. 3. Philadelphia, PA: Society for Industrial and Applied Mathematics. pp. 172–174. ISBN 978-0-898714-32-6. Zbl 0919.05001. <a href="978-0-898714-32-6" target="_blank">978-0-898714-32-6</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>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. <a href="/wiki/David_Eppstein" target="_blank">/wiki/David_Eppstein</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>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. <a href="/wiki/Robert_Tarjan" target="_blank">/wiki/Robert_Tarjan</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>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. S2CID 16082154. <a href="/wiki/Takao_Nishizeki" target="_blank">/wiki/Takao_Nishizeki</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>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) <a href="https://doi.org/10.1016%2F0166-218X%2894%2990022-1" target="_blank">https://doi.org/10.1016%2F0166-218X%2894%2990022-1</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> </ol>