ONLINE MAINTENANCE OF TRICONNECTED COMPONENTS WITH SPQR-TREES

We consider the problem of maintaining on-line the triconnected compon ents of a graph G. Let n be the current number of vertices of G. We pr esent an O (rt)-space data structure that supports insertions of verti ces and edges, and queries of the type ''Are there three vertex-disjoi nt 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 t he well-known Ackermann's function inverse), and time O(n log n + k) i f G is not biconnected. Note that the bounds do not depend on the numb er of edges of G. We use the SPQR-tree, a versatile data structure tha t represents the decomposition of a biconnected graph with respect to its triconnected components, and the BC-tree, which represents the dec omposition of a connected graph with respect to its biconnected compon ents.