A Linear Time Implementation of SPQR-Trees

Gutwenger, Carsten and Mutzel, Petra (2001) A Linear Time Implementation of SPQR-Trees. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000 , pp. 77-90(Official URL: http://dx.doi.org/10.1007/3-540-44541-2_8).

Full text not available from this repository.


The data structure SPQR-tree represents the decomposition of a biconnected graph with respect to its triconnected components. SPQR-trees have been introduced by Di Battista and Tamassia [8] and, since then, became quite important in the field of graph algorithms. 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. We describe the relationship between SPQR-trees and triconnected components and apply the resulting algorithm to the computation of SPQR-trees. Our implementation is publically available in AGD [1].

Item Type: Conference Paper
Additional Information: 10.1007/3-540-44541-2_8
Classifications: G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
G Algorithms and Complexity > G.770 Planarity Testing
URI: http://gdea.informatik.uni-koeln.de/id/eprint/306

Actions (login required)

View Item View Item