Talk:Series–parallel graph

A fact from Series–parallel graph appeared on Wikipedia's Main Page in the Did you know column on 11 March 2007. The text of the entry was as follows: Did you know... that a series-parallel graph is a mathematical model of series and parallel electric circuits with two different nodes called source and sink, indicating the direction of the electrical current flow? A record of the entry may be seen at Wikipedia:Did you know archive/2007/March.

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

The Properties section of the article contains a paragraph that previously read as follows:

Every series-parallel graph has treewidth at most 2 and branchwidth at most 2. 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.^[1][2] 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. Graphs of treewidth at most 2 have an explicit forbidden minor characterization, implying that a graph is series-parallel if and only if its biconnected components are linked in a path and it excludes the complete graph K₄ as a minor.

But the last sentence, claiming that a graph is series-parallel if and only if its biconnected components are linked in a path and it excludes the complete graph K₄ as a minor, is false, as the Wheatstone bridge graph shows:

This graph is connected, its biconnected components are linked in a path, and it does not contain K₄ as a minor, but it is not a series-parallel graph.

Therefore, I have removed the last sentence of this paragraph. —Bkell (talk) 18:09, 28 May 2013 (UTC)Reply

I think a corrected characterization is: G is series-parallel for terminals s and t iff the graph formed from G by adding an edge st is biconnected and has no K4 minor. But I agree, something like this should be sourced. —David Eppstein (talk) 20:34, 28 May 2013 (UTC)Reply

The definition 2 is not consistent with the characterisation on complete graph K₄ minor : it is evident that any tree has no K₄ minor, while cannot be reduced to a K₂ under the operation described. . —Alexanderlai (talk) 11:20 29 Nov 2016 (UTC)

Hello,

in the Section 'Computational complexity' it is claimed that the recognition of SP graphs is possible in linear time, while the linked paper just shows the linear time recognition of SP digraphs. Please add https://www.win.tue.nl/~berry/papers/CS-R9504.pdf A New Algorithm for the Recognition of Series Parallel Graphs - Berry Schoenmakers as addition to the citing. In the papaer is a linear time algorithm explained, which proofs the claim on the wiki page.

Best regards — Preceding unsigned comment added by 91.32.185.89 (talk) 20:14, 16 April 2022 (UTC)Reply

As a never-published tech report that seems unlikely to be the best reference for that claim. Other papers from the time of Valdez et al (long before this tech report) treat the existence of a linear time algorithm as well known and cite Valdez et al for the main ideas. See for instance the remarks following procedure TEST on page 84 of "Combinatorial problems on series-parallel graphs", K. Takamizawa, T. Nishizeki & N. Saito, 1982, doi:10.1007/3-540-10704-5_8, which states the linear time recognition of undirected series-parallel graphs as known, with Valdez et al as one of the references. The other two references it gives for this fact are Hopcroft and Tarjan "Dividing a graph into triconnected components" 1973 (which finds the appropriate decomposition in linear time leaving as the only remaining task verifying that each of the triconnected components is a cycle or a bond graph) and a paper by the same Japanese authors in Trans. IEICE 1976. —David Eppstein (talk) 23:06, 16 April 2022 (UTC)Reply

The definition of series composition is that the source of one merges with the sink of another. However, the picture here https://en.wikipedia.org/wiki/Series%E2%80%93parallel_graph#/media/File:Series_parallel_composition.svg has the sink of one graph connected to the other by an edge. 23.92.12.90 (talk) 17:14, 14 January 2025 (UTC)Reply

That edge was part of one the two subgraphs that were composed; it was not added as part of the composition operation. —David Eppstein (talk) 18:11, 14 January 2025 (UTC)Reply