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:
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 articles
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.[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 K4 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 K4 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 K4 as a minor, but it is not a series-parallel graph.
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 K4minor : it is evident that any tree has no K4 minor, while
cannot be reduced to a K2 under the operation described.
. â
Alexanderlai (
talk) 11:20 29 Nov 2016 (UTC)
^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.
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.
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