On-line maintenance of triconnected components with SPQR-trees

Abstract

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 verticesv1 andv2?" A sequence of k operations takes time O.k¢fi.k;n// if G is biconnected (fi.k;n/ denotes the well-known Ackermann's function inverse), and timeO.n log nC 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.