SPQR-Trees

SPQR-trees are a versatile data structure, which essentially represents the decomposition of a biconnected graph with respect to its triconnected components [DT96a]. Moreover, if G is a planar, biconnected graph, then its SPQR-tree represents all possible embeddings of G [DT96b].

We support only the statical construction of an SPQR-tree for a given graph, dynamic updates as described in [DT96a,DT96b] are not supported. The class SPQRTree implements SPQR-trees for general biconnected graphs. Additional functionality for representing all embeddings of a planar, biconnected graph is provided by the class PlanarSPQRTree, which is derived from SPQRTree. Both classes use the two auxiliary classes Skeleton and PertinentGraph.