an edge in Gx and the other of which is an edge in Gy. Each edge in a graph Gx may be a virtual edge for at most one SPQR tree edge. An SPQR tree T represents a 2-connected graph GT, formed as follows. Whenever SPQR tree edge xy associates the virtual edge ab of Gx with the virtual edge cd of Gy, form a single larger graph by merging a and c into a single supervertex, merging b and d into another single supervertex, and deleting the two virtual edges. That is, the larger graph is the 2-clique-sum of Gx and Gy. 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. Each vertex in one of the graphs Gx may be associated in this way with a unique vertex in GT, the supervertex into which it was merged. Typically, it is not allowed within an SPQR tree for two S nodes to be adjacent, nor for two P nodes to be adjacent, because if such an adjacency occurred the two nodes could be merged into a single larger node. With this assumption, the SPQR tree is uniquely determined from its graph. When a graph G is represented by an SPQR tree with no adjacent P nodes and no adjacent S nodes, then the graphs Gx associated with the nodes of the SPQR tree are known as the triconnected components of G. Construction The SPQR tree of a given 2-vertex-connected graph can be constructed in linear time. The problem of constructing the triconnected components of a graph was first solved in linear time by . Based on this algorithm, suggested that the full SPQR tree structure, and not just the list of components, should be constructible in linear time. After an implementation of a slower algorithm for SPQR trees was provided as part of the GDToolkit library, provided the first linear-time implementation. As part of this process of implementing this algorithm, they also corrected some errors in the earlier work of . The algorithm of includes the following overall steps. Sort the edges of the graph by the pairs of numerical indices of their endpoints, using a variant of radix sort that makes two passes of bucket sort, one for each endpoint. After this sorting step, parallel edges between the same two