Talk:SPQR tree

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

It would be useful first of all to clarify whether the connectivity involved is edge-connected or vertex-connected, or whether both variants fall out of the same algorithm. MaxEnt 01:44, 15 August 2007 (UTC)[reply]

Apparently there's an implementation in the AGD library (free for academic use) on top of LEDA (proprietary licenses only). See the ADG SPQR Tree manual. MaxEnt 03:07, 15 August 2007 (UTC)[reply]

There's an implementation in ogdf [1] which is the successor to AGD and does not depend on LEDA. Note that the implementors of OGDF claim in [2] that the algorithm described in the original papers of Battista and Tamassia (cited on this page) was buggy: "Theoretical papers using SPQR-trees claim that they can be implemented in linear time using a modification of the algorithm by Hopcroft and Tarjan [15] for decomposing a graph into its triconnected components. So far no correct linear time implementation of either triconnectivity decomposition or SPQR-trees is known to us. Here, we show the incorrectness of the Hopcroft and Tarjan algorithm [15], and correct the faulty parts." I haven't read the details of their claim (only an abstract is on the web). It's not clear to me if they mean that the Hopcroft-Tarjan algorithm itself was buggy, or that it doesn't work in this context. Ajb (talk) 21:27, 21 June 2009 (UTC)[reply]

Unrooted version definition

I checked all the references cited in this article, and none of them defines the SPQR tree as this article does. Differences are minimal, such as the tree being rooted, directed or having an extra Q node. So I am asking if anyone knows the author of this nice definition published here in Wikipedia. 148.218.36.14 (talk) 22:52, 20 June 2013 (UTC)[reply]

Most of the content currently in the article was written by me in 2009. It was not my intention to introduce differences from the literature, but I think rooting the tree would be a mistake: as an unrooted tree it is uniquely defined, as a rooted tree it is not. The Q nodes are a bit more problematic as different sources use or don't use them for different things. FWIW I believe that the definitions here are the same as the ones in my own recent papers that use SPQR trees e.g. at SoCG 2010 and 2013. —David Eppstein (talk) 02:57, 22 June 2013 (UTC)[reply]

Where is Tutte?

The so-called (and one could argue mis-named) "SPQR tree" was introduced by Tutte in order to describe the structure of 2-separations of a 3-connected graph. All the terminology and references in this article seem to have been written in ignorance of Tutte's 3-block decomposition and his terminology. That ought to be corrected by someone who knows enough history. I ought to but I'm too busy currently. A good reference is Tutte's textbook Graph Theory (1984). I can't give the original reference; none of my reference works is with me now. Zaslav (talk) 23:14, 16 April 2016 (UTC)[reply]

In this our article follows much of the recent literature on the subject, which also unfortunately ignores Mac Lane's contributions and even that of Hopcroft and Tarjan (already mentioned here) and instead acts as if this structure was first invented by Di Battista and Tamassia, even though D & T themselves cited some of this earlier work. If you do find the missing references please list them here so they can be included. —David Eppstein (talk) 23:53, 16 April 2016 (UTC)[reply]

I will when I can but still don't have my books accessible. Zaslav (talk) 05:29, 29 September 2017 (UTC)[reply]

Unclear sentence

Construction:Sentence

with its edges oriented away from the root of the tree, for the edges belonging to the tree, and towards the root for all other edges

is not clear - what other edges? What edges may contains tree, that do not belong to tree? Jumpow (talk) 17:57, 13 September 2017 (UTC)[reply]

The context is depth-first search in a graph. The tree is a depth-first-search tree of the graph. The "other edges" are the edges of the graph that are not included in this tree. The key property of depth-first search trees, used here, is that every non-tree edge of the graph connects an ancestor-descendant pair in the tree, so "towards the root" is unambiguous even for the non-tree edges. —David Eppstein (talk) 18:18, 13 September 2017 (UTC)[reply]

I think, first tree have to be replaced by palm and good insert image of palm (I may create image like palm in article of Gutwenger & Mutzel, maybe in more simple form) Jumpow (talk) 19:07, 13 September 2017 (UTC)[reply]

In what language is "palm" correct terminology for this concept? I don't recall ever seeing it? —David Eppstein (talk) 19:40, 13 September 2017 (UTC)[reply]

use depth-first search to find a structure that they call a palm tree; this is a depth-first search tree with its edges oriented away from the root of the tree, for the edges belonging to the tree, and towards the root for all other edges.

So, depth-first search tree is palm tree Jumpow (talk) 19:58, 13 September 2017 (UTC)[reply]

No. "Palm tree" is clearly defined in this very article, as a structure giving an orientation to all of the edges of the graph. So it would be incorrect to then talk about the edges in the palm and the edges not in the palm. It is the edges in the depth-first-search tree and the edges not in that tree that we need to distinguish from each other. —David Eppstein (talk) 20:46, 13 September 2017 (UTC)[reply]

Node orientation

Representing all embeddings of planar graphs:

it is possible to flip the orientation of one of the nodes relative to the other one...

What is orientation of node? Jumpow (talk) 19:37, 13 September 2017 (UTC)[reply]

See Orientability. If you replace a node by its mirror image, you are changing its orientation.

As I understand, node = point. What is orientation of point?

Also, if look at image above, SPQR tree does not have any orientation... Jumpow (talk) 19:48, 13 September 2017 (UTC)[reply]

Each node of the SPQR tree represents a graph. In the case of planar graphs and R nodes or S nodes, that graph has a planar embedding that is unique *up to the choice of orientation*. (P nodes are treated separately in that part of our article.) —David Eppstein (talk) 20:36, 13 September 2017 (UTC)[reply]

Oops! I missed Each edge xy between two nodes of the SPQR tree is associated with two directed virtual edges. Thank you! Jumpow (talk) 20:54, 13 September 2017 (UTC)[reply]