Abstract
We consider graphs whose vertices may be in one of two different states: either on or off. We wish to maintain dynamically such graphs under an intermixed sequence of updates and queries. An update may reverse the status of a vertex, by switching it either on or off, and may insert a new edge or delete an existing edge. A query tests properties of the subgraph induced by the vertices that are on. We give efficient algorithms that maintain information about connectivity on planar graphs in O(log3 n) amortized time per query, insert, delete, switch-on and switch-off operation over sequences of at least Ω(n) operations, where n is the number of vertices of the graph.
Work supported in part by EU ESPRIT Long Term Research Project ALCOMIT under contract no. 20244, and by the Italian MURST Project “Eflicienza di Algoritmi e Progetto di Strutture Informative”. The research of the second author was supported in part also by a Research Grant from University “Ca' Foscari” of Venice and by the German-Italian Program “Vigoni 1997”.
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
D. Alberts and G. Cattaneo and G. F. Italiano. An empirical study of dynamic graph algorithms. Proc. 7th ACM-SIAM Symp. Discrete Algorithms, 1996, 192–201.
D. Alberts and M. R. Henzinger. Average case analysis of dynamic graph algorithms. Proc. 6th ACM-SIAM Symp. Discrete Algorithms, 1995, 312–321.
G. Amato, G. Cattaneo, G. F. Italiano. Experimental analysis of dynamic minimum spanning tree algorithms. Proc. 8th ACM-SIAM Symp. on Discrete Algorithms, 1997, 314–323.
D. Eppstein, Z. Galil, G.F. Italiano, and A. Nissenzweig. Sparsification—A technique for speeding up dynamic graph algorithms. Proc. 93rd IEEE Symp. on Foundations of Computer Science, 1992, 60–69.
D. Eppstein, Z. Galil, G. F. Italiano, T. H. Spencer, “Separator based sparsification 1: planarity testing and minimum spanning trees”, Journal of Computer and System Science, Special issue of STOC 93, vol. 52, no. 1 (1996), 3–27.
D. Eppstein, Z. Galil, G. F. Italiano, T. H. Spencer, “Separator based sparsification II: edge and vertex connectivity”, SIAM J. Comput., to appear.
D. Eppstein, G.F. Italiano, R. Tamassia, R.E. Tarjan, J. Westbrook, and M. Yung. Maintenance of a minimum spanning forest in a dynamic plane graph. J. Algorithms 13 (1992), 33–54.
G.N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14 (1985), 781–798.
G.N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. Proc. 32nd IEEE Symp. Foundations of Computer Science, 1991, 632–641.
D. Frigioni, A. Marchetti-Spaccamela, U. Nanni. Fully dynamic output bounded single source shortest path problem. Proc. 7th ACM-SIAM Symp. Discrete Algorithms, 1996, 212–221.
Z. Galil, G.F. Italiano, and N. Sarnak. Fully dynamic planarity testing. Proc. 24th ACM Symp. Theory of Computing, 1992, 495–506.
M.T. Goodrich. Planar separators and parallel polygon triangulation. Proc. 24th ACM Symp. Theory of Computing, 1992, 507–516.
M. Rauch Henzinger and V. King. Randomized dynamic graph algorithms with polylogarithmic time per operation. Proc. 27th ACM Symp. on Theory of Computing, 1995, 519–527.
M. Rauch Henzinger and V. King. Fully dynamic biconnectivity and transitive closure, Proc. 36th IEEE Symp. Foundations of Computer Science, 1995.
M. Rauch Henzinger and V. King. Maintaining minimum spanning trees in dynamic graphs. Proc. 24th Int. Coll. on Automata, Languages and Programming, 1997.
M. Rauch Henzinger and J. A. La Poutré. Certificates and fast algorithms for biconnectivity in fully dynamic graphs. Proc. 3rd European Symp. on Algorithms. Springer-Verlag LNCS 979 1995, 171–184.
M. Rauch Henzinger and M. Thorup. Improved sampling with applications to dynamic algorithms. Proc. 23rd Int. Coll. on Automata, Languages and Programming. Springer-Verlag LNCS 1099, 1996, 290–299.
J. Herschberger, M. Rauch and S. Suri. Fully dynamic 2-connectivity on planar graphs. Proc. 3rd Scandinavian Workshop on Algorithm Theory. Springer-Verlag LNCS 621, 1992, 233–244.
R. J. Lipton, R. E. Tarjan. A separator theorem for planar graphs, SIAM J. Appl. Math. 36 (1979), 177–189.
M. Rauch. Fully dynamic biconnectivity in graphs. Proc. 33rd IEEE Symp. Foundations of Computer Science, 1992, 50–59.
M. Rauch. Improved data structures for fully dynamic biconnectivity. Proc. 26th ACM Symp. on Theory of Computing, 1994, 686–695.
D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. J. Comput. System Sci., 26 (1983), 362–391.
M. Thorup. Decremental dynamic connectivity. Proc. 8th ACM-SIAM Symp. on Discrete Algorithms, 1997, 305–313.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Frigioni, D., Italiano, G.F. (1997). Dynamically switching vertices in planar graphs. In: Burkard, R., Woeginger, G. (eds) Algorithms — ESA '97. ESA 1997. Lecture Notes in Computer Science, vol 1284. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63397-9_15
Download citation
DOI: https://doi.org/10.1007/3-540-63397-9_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63397-6
Online ISBN: 978-3-540-69536-3
eBook Packages: Springer Book Archive