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 (rt)-space data structure that supports insertions of vertices and edges, and queries of the type ''Are there three vertex-disjoint paths between vertices v(1) and v(2)?'' A sequence of k operations takes time O(k . alpha(k,n)) if G is biconnected (alpha(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.