Talk:Series–parallel graph

Removed: apparently false characterization of series-parallel graphs

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. 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)

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)

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)

References

Computational recognition of SP-graphs - reference is missleading

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)

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)