SPQR tree

The basic structures underlying the SPQR tree, the triconnected components of a graph, and the connection between this decomposition and the planar embeddings of a planar graph, were first investigated by Saunders Mac Lane (1937); these structures were used in efficient algorithms by several other researchers[2] prior to their formalization as the SPQR tree by Di Battista and Tamassia (1989, 1990, 1996).

Performing this gluing step on each edge of the SPQR tree produces the graph GT; the order of performing the gluing steps does not affect the result.

[1] The problem of constructing the triconnected components of a graph was first solved in linear time by Hopcroft & Tarjan (1973).

Based on this algorithm, Di Battista & Tamassia (1996) suggested that the full SPQR tree structure, and not just the list of components, should be constructible in linear time.

As part of this process of implementing this algorithm, they also corrected some errors in the earlier work of Hopcroft & Tarjan (1973).