SPQR tree

A graph and its SPQR tree. The dashed black lines connect pairs of virtual edges, shown as black; the remaining edges are colored according to the triconnected component they belong to.

In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time[1] and has several applications in dynamic graph algorithms and graph drawing.

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).

  1. ^ Hopcroft & Tarjan (1973); Gutwenger & Mutzel (2001).
  2. ^ E.g., Hopcroft & Tarjan (1973) and Bienstock & Monma (1988), both of which are cited as precedents by Di Battista and Tamassia.