Maintenance of a minimum spanning forest in a dynamic planar graph

David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert E. Tarjan, Jeffery Westbrook, Moti Yung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations

Abstract

We give efficient algorithms for maintaining a minimum spanning forest of a planar graph subject to on-line modifications. The modifications supported include changes in the edge weights, and insertion and deletion of edges and vertices. To implement the algorithms, we develop a data structure called an edge-ordered dynamic tree, which is a variant of the dynamic tree data structure of Sleator and Tarjan. Using this data structure, our algorithms run in O(logn) time per operation and O(n) space. The algorithms can be used to maintain the connected components of a dynamic planar graph in O(logn) time per operation.

Original languageEnglish (US)
Title of host publicationProceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990
PublisherAssociation for Computing Machinery
Pages1-11
Number of pages11
ISBN (Electronic)0898712513
StatePublished - Jan 1 1990
Externally publishedYes
Event1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990 - San Francisco, United States
Duration: Jan 22 1990Jan 24 1990

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990
CountryUnited States
CitySan Francisco
Period1/22/901/24/90

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Maintenance of a minimum spanning forest in a dynamic planar graph'. Together they form a unique fingerprint.

  • Cite this

    Eppstein, D., Italiano, G. F., Tamassia, R., Tarjan, R. E., Westbrook, J., & Yung, M. (1990). Maintenance of a minimum spanning forest in a dynamic planar graph. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990 (pp. 1-11). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery.