Abstract
The incremental planarity testing problem is to perform the following operations on a biconnected planar graph G of at most n vertices: test if an edge can be added between two vertices while preserving planarity; add edges and vertices that preserve planarity. Let m be the total number of operations. We present fast data structures for this problem that can be used in conjunction with the previous algorithm of Di Battista and Tamassia to achieve an O(α(m, n)) worst-case amortized time per test operation. If the graph is biconnected, a sequence of n additions can be performed in total time O(mα(m, n)) worst-case plus O(n) expected time. Our tree data structure is flexible and can answer in O(1) time queries about parents, roots, and nearest common ancestors while performing tree modifications such as inserting nodes, cutting edges, and merging or splitting nodes. If the graph is not biconnected then insertions of edges and vertices require O(log n) amortized expected time per operation.
Research partially supported by National Science Foundation Grant CCR-9008653.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. D. Battista and R. Tamassia. Incremental planarity testing. In Proc. 30th IEEE FOCS, pages 436–441, 1989.
G. D. Battista and R. Tamassia. On-line graph algorithms with SPQR-trees. In Proc. 17th ICALP, 1990.
K. Booth and G. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci., 13:335–379, 1976.
P. F. Deitz and D. D. Sleator. Two algorithms for maintaining order in a list. In Proc. 19th ACM STOC, pages 365–372, 1987.
M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. M. auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: upper and lower bounds. In Proceedings 29th IEEE FOCS, pages 524–531, 1988.
M. L. Fredman and M. E. Saks. The cell probe complexity of dynamic data structures. In Proc. 21st ACM STOC, pages 345–354, Seattle, WA, May 1989.
H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proc. 1st ACM-SIAM SODA, pages 434–443, 1990.
H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci., 30:209–211, 1985.
F. Harary. Graph Theory. Addison-Wesley, Reading, MA., 1972.
D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput, 13(2):338–355, 1984.
J. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM J. Comput, 2:135–158, 1973.
J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21:549–568, 1974.
H. Imai and T. Asano. Dynamic orthogonal segment intersection search. Journal of Algorithms, 8:1–18, 1987.
G. F. Italiano and Z. Galil. Fully dynamic algorithms for edge connectivity problems. In 23rd ACM STOC, pages 317–327, 1991.
J.A. La Poutré. Lower bounds for the union-find and split-find problems on pointer machines. In Proc. 22nd ACM Symposium on Theory of Computing, pages 34–44, 1990.
J. A. La Poutré. On-line maintenance of triconnected components. These proceedings.
V. Ramachandran and J. H. Reif. An optimal parallel algorithm for graph planarity. In Proc. 30th FOCS, pages 282–287, 1989.
R. E. Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM, 22:215–225, 1975.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Westbrook, J. (1992). Fast incremental planarity testing. In: Kuich, W. (eds) Automata, Languages and Programming. ICALP 1992. Lecture Notes in Computer Science, vol 623. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-55719-9_86
Download citation
DOI: https://doi.org/10.1007/3-540-55719-9_86
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55719-7
Online ISBN: 978-3-540-47278-0
eBook Packages: Springer Book Archive