Fully dynamic planarity testing (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fully dynamic planarity testing (extended abstract)

Full text

Pdf (1.41 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 495 - 506

Year of Publication: 1992

ISBN:0-89791-511-9

Authors

Zvi Galil	Department of Computer Science, Columbia University, and Tel-Aviv University
Giuseppe F. Italiano	IBM T. J. Watson Research Center, P.O. Box 704, Yorktown, Heights, NY and Università di Roma, Italy
Neil Sarnak	IBM T. J. Watson Research Center, P.O. Box 704, Yorktown, Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 17, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/129712.129761 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Daniel Bienstock , Clyde L. Monma, On the complexity of covering vertices by faces in a planar graph, SIAM Journal on Computing, v.17 n.1, p.53-76, Feb. 1988 [doi>10.1137/0217004]
	3	G. Di Battista and R. Taxaassia. Incremental planarity testing. In Proc. 30th Annual Syrup. on Foundations of Computer Science, pages 436-441, 1989.
	4	Giuseppe Di Battista , Roberto Tamassia, On-line graph algorithms with SPQR-trees, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.598-611, July 1990, Warwick University, England
	5	David Eppstein , Giuseppe F. Italiano , Roberto Tamassia , Robert E. Tarjan , Jeffery Westbrook , Moti Yung, Maintenance of a minimum spanning forest in a dynamic planar graph, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.1-11, January 22-24, 1990, San Francisco, California, United States
	6	G. N. Frederickson. Data structures for on-line updating of minimum spanning trees. SIAM J. Comput., 14:781-798, 1985.
	7	Greg N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, v.16 n.6, p.1004-1022, December 1, 1987 [doi>10.1137/0216064]
	8	Greg N. Frederickson, Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees, Proceedings of the 32nd annual symposium on Foundations of computer science, p.632-641, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185429]
	9	Zvi Galil , Giuseppe F. Italiano, Fully dynamic algorithms for edge connectivity problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.317-327, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103454]
	10	Zvi Galil , Giuseppe F. Italiano, Maintaining biconnected components of dynamic planar graphs (extended abstract), Proceedings of the 18th international colloquium on Automata, languages and programming, p.339-350, June 1991, Madrid, Spain
	11	F. Harary. Graph Theory. Addison-Wesley, Reading, MA, 1969.
	12	J. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2:135- 158, 1973.
	13	John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
	14	J. A. La Poutr#. Personal communication, 1992.
	15	R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36:177-189, 1979.
	16	Roberto Tamassia, A Dynamic Data Structure for Planar Graph Embedding (Extended Abstract), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.576-590, July 11-15, 1988
	17	R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1:146-160, 1972.
	18	W. T. Tutte. Connectivity in graphs. University of Toronto Press, 1966.
	19	Jeffery Westbrook, Fast Incremental Planarity Testing, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.342-353, July 13-17, 1992

CITED BY 4

	Zvi Galil , Giuseppe F. Italiano , Neil Sarnak, Fully dynamic planarity testing with applications, Journal of the ACM (JACM), v.46 n.1, p.28-91, Jan. 1999
	Philip Klein , Satish Rao , Monika Rauch , Sairam Subramanian, Faster shortest-path algorithms for planar graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.27-37, May 23-25, 1994, Montreal, Quebec, Canada
	David Eppstein , Zvi Galil , Giuseppe F. Italiano , Thomas H. Spencer, Separator based sparsification for dynamic planar graph algorithms, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.208-217, May 16-18, 1993, San Diego, California, United States
	Joel Seiferas, Reprints from Computing Reviews, ACM SIGACT News, v.31 n.2, p.12-13, June 1 2000