On-line maintenance of triconnected components with SPQR-trees.

We consider the problem of maintaining on-line the triconnected components of a graph G. Let n be the current number of vertices of G. We present an O(n)-space data structure that supports insertions of vertices and edges, and queries of the type 'Are there three vertex-disjoint paths between vertices v and v?' A sequence of k operations takes time O(k·α(k, n)) if G is biconnected (α(k, n) denotes the well-known Ackermann's function inverse), and time O( n log n+ k) if G is not biconnected. Note that the bounds do not depend on the number of edges of G. We use the SPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and the BC-tree, which represents the decomposition of a connected graph with respect to its biconnected components. [ABSTRACT FROM AUTHOR]