SP(Q)R Trees
An SPQR tree decomposes the triconnected components of a biconnected graph by removing pairs of cut-vertices and storing them in a tree-structure.
Below references two other works, Hopcroft and Tarjan provided the first linear time solution for constructing such a tree, and Gutwenger and Mutzel provided the first linear-time implementation of constructing such a tree. Links to these works are in the credits section of this site.
For this proof, a simplified version of the SPQR tree, the SPR tree is utilized, and its linear time implementation is important to the overall complexity of the algorithm presented. SPR trees do not differ from SPQR trees in any way besides excluding Q-nodes.
Decomposes biconnected graphs into triconnected components in linear time. (theoretically)
Nodes: Defined by skeletons, which are smaller subgraphs that can be defined as S, P, Q, or R nodes.
(Brief) Overview of linear-time implementation
1. Sort edges by endpoint index (radix sort with 2 passes, for each endpoint)
2. Find cut edges
3. Find split components
4. Merge
O(n) Time complexity
Skeletons for SPR graph
S-Node
Simple cycle with ≥ 3 vertices
P-Node
Two vertices connected by ≥ 3 edges
µ are children of a given P node. Each of the children are defined a convex polygon and they will be either S or R-Nodes.
R Node
Simple triconnected graph
SPR tree in our problem
- Remove crossing edges. Result is a planar subgraph.
- Root node: Skeleton contains vertices on the outer face
- Recurse through tree from top. At each node
- Construct convex drawing in linear time. (via Chiba et al.)
- Re-insert crossing edges as straight-lines
- Replace corresponding virtual edge with convex drawing of each child starting at the level above leaf nodes.
Recall the properties of red-maximal graphs, we can make the following assumptions about the polygonal shapes of each type of node as a result.
1. Property 6 (the outer face will be a 3 or 4 cycle): The root of our SPR tree will be an R-node in case of a 3-cycle or an S-node in case of a 4-cycle.
2. Property 4: A 4-cycle ony exists on faces with a crossing vertex or surrounding a crossing. As crossing edges are removed prior to the construction of the SPR tree, these cycles will not exist in the planar subgraph, or will not form a triconnected component without the crossing.
3. The skeleton of an S-node is either a 3 or 4 cycle.
- For the same reasoning as above, triangulated faces as well as 4-cycles which surrounded crossings in our red-maximal graph will be represented as S-nodes.
Through the linear time construction of the SPR tree, a straight-line drawing of the red-maximal graph is produced.
Using the observations we can define polygons for each node.
R-Nodes: In case of root: A triangle is defined, as the outer face is a 3-cycle as mentioned above.
Left/Right triangle in case of a real edge
Rhombus in case of a virtual edge
S-Nodes: In case of root: a rectangle is defined (4-cycle as mentioned above)
Triangle or trapezoid (3-cycle or 4-cycle)
P-Nodes: Defines polygonal shapes for children R or S nodes.
Examples of the shapes are below.
Left/Right Triangle(s)
One possibility is that the virtual edge exists creating a P-node. In cases such as the one illustrated above, the child of the P-node is an R-node with a 4-cycle as its outer face, creating a left and/or right triangle.
Rhombus
In a case similar to the left/right triangles, if the virtual edge does not exist in the graph and only exists for decomposition, a rhombus will be constructed
Trapezoid
In cases where there is a cycle and an S-node is used, then there will be a trapezoid.
Important note: This ability to predetermine polygonal shapes for certain nodes is crucial to the time complexity of this algorithm. The algorithm by Chiba et al. for constructing a straight-line drawing of a convex polygon requires a valid input graph, which is guaranteed in this case.