Abstract
We consider the problem of maintaining on-line the triconnected components of a graphG. Letn be the current number of vertices ofG. We present anO(n)-space data structure that supports insertions of vertices and edges, and queries of the type “Are there three vertex-disjoint paths between verticesv 1 andv 2?” A sequence ofk operations takes timeO(k·α(k, n)) ifG is biconnected(α(k, n) denotes the well-known Ackermann's function inverse), and timeO(n logn+k) ifG is not biconnected. Note that the bounds do not depend on the number of edges ofG. We use theSPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and theBC-tree, which represents the decomposition of a connected graph with respect to its biconnected components.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. Di Battista and R. Tamassia, Incremental Planarity Testing,Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 436–441.
G. Di Battista and R. Tamassia, On-Line Planarity Testing,SIAM Journal on Computing,25(5) (1996), to appear.
D. Fussell, V. Ramachandran, and R. Thurimella, Finding Triconnected Components by Local Replacements,Automata, Languages and Programming (Proc. 16th ICALP), Lecture Notes in Computer Science, Vol. 372, Springer-Verlag, Berlin, 1989, pp. 379–393.
H. N. Gabow and R. E. Tarjan, A Linear Time Algorithm for a Special Case of Disjoint Set Union,J. Comput. Systems Sci.,30 (1985), 209–221.
J. Hopcroft and R. E. Tarjan, Dividing a Graph into Triconnected Components,SIAM J. Comput.,2 (1973), 135–158.
H. Imai and T. Asano, Dynamic Orthogonal Segment Intersection Search,J. Algorithms,8 (1987), 1–18.
A. Kanevsky, A Characterization of Separating Pairs and Triplets in a Graph,Congress. Numer.,74 (1990), 213–232.
J. A. La Poutré, Maintenance of Triconnected Components of Graphs,Automata, Languages and Programming (Proc. 19th ICALP), Lecture Notes in Computer Science, Vol. 623, Springer-Verlag, Berlin, 1992, pp. 354–365.
R. Tamassia, On-Line Planar Graph Embedding,J. Algorithms (to appear). (Preliminary version inProc. 15th ICALP, Lecture Notes in Computer Science, Vol. 317, Springer-Verlag, Berlin, 1988, pp. 576–590.)
R. E. Tarjan, Amortized Computational Complexity,SIAM J. Algebraic Discrete Methods,6 (1985), 306–318.
R. E. Tarjan and J. van Leeuwen, Worst-Case Analysis of Set-Union Algorithms,J. Assoc. Comput. Mach.,31 (1984), 245–281.
W. T. Tutte,Graph Theory, Encyclopedia of Mathematics and Its Applications, Vol. 21, Addison-Wesley, Reading, MA, 1984.
J. Westbrook and R. E. Tarjan, Maintaining Bridge-Connected and Biconnected Components On-Line,Algorithmica,7 (1992), 433–464.
Author information
Authors and Affiliations
Additional information
Communicated by T. Nishizeki.
This research was supported in part by the National Science Foundation under Grant CCR-9007851, by the U.S. Army Research Office under Grants DAAL03-91-G-0035 and DAAH04-93-0134, by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA Order 8225, by the NATO Scientific Affairs Division under Collaborative Research Grant 911016, by the Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the Italian National Research Council, and by the Esprit II BRA of the European Community (project ALCOM). An extended abstract of this paper was presented at the 17th International Colloquium on Automata, Languages, and Programming, Warwick, 1990.
Work performed in part while this author was with the Università di Roma “La Sapienza,” Dipartimento di Informatica e Sistemistica.
Rights and permissions
About this article
Cite this article
Di Battista, G., Tamassia, R. On-line maintenance of triconnected components with SPQR-trees. Algorithmica 15, 302–318 (1996). https://doi.org/10.1007/BF01961541
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01961541