vertices will be adjacent to each other in the sorted list and can be split off into a P-node of the eventual SPQR tree, leaving the remaining graph simple. Partition the graph into split components; these are graphs that can be formed by finding a pair of separating vertices, splitting the graph at these two vertices into two smaller graphs (with a linked pair of virtual edges having the separating vertices as endpoints), and repeating this splitting process until no more separating pairs exist. The partition found in this way is not uniquely defined, because the parts of the graph that should become S-nodes of the SPQR tree will be subdivided into multiple triangles. Label each split component with a P (a two-vertex split component with multiple edges), an S (a split component in the form of a triangle), or an R (any other split component). While there exist two split components that share a linked pair of virtual edges, and both components have type S or both have type P, merge them into a single larger component of the same type. To find the split components, 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. They then find a special preorder numbering of the nodes in the tree, and use certain patterns in this numbering to identify pairs of vertices that can separate the graph into smaller components. When a component is found in this way, a stack data structure is used to identify the edges that should be part of the new component. Usage Finding 2-vertex cuts With the SPQR tree of a graph G (without Q nodes) it is straightforward to find every pair of vertices u and v in G such that removing u and v from G leaves a disconnected graph, and the connected components of the remaining graphs: The two vertices u and v may be the two endpoints of a virtual edge in the graph associated with an R node, in which case the two components are represented by the two subtrees of the SPQR tree formed by removing the corresponding SPQR tree edge. The two vertices u and v may be the two vertices in the