TY - JOUR

T1 - Maintenance of a minimum spanning forest in a dynamic plane graph

AU - Eppstein, David

AU - Italiano, Giuseppe F.

AU - Tamassia, Roberto

AU - Tarjan, Robert E.

AU - Westbrook, Jeffery

AU - Yung, Moti

N1 - Funding Information:
*Research supported in part by NSF Grants CCR-88-14977, DCR-86-05962, CCR-90-09753, ONR Contract NOOO14-91-J-1463, DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant NSF-STC88-09648, and Esprit II Basic Research Actions Program of the European Communities Contract 3075. A preliminary version of this article appeared in the “Proceedings 1st ACM-SIAM Symposium on Discrete-Algorithms, San Francisco, CA, January 1990.” ‘This work was done while the author was at the Department of Computer Science, Columbia University, New York, NY 10027. *Partially supported by an IBM Graduate Fellowship. *This work done while the author was at the Department of Computer Science, Princeton University.

PY - 1992/3

Y1 - 1992/3

N2 - We give an efficient algorithm for maintaining a minimum spanning forest of a plane graph subject to on-line modifications. The modifications supported include changes in the edge weights and insertion and deletion of edges and vertices which are consistent with the given embedding. 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 algorithm runs in O(log n) time per operation and O(n) space. The algorithm can be used to maintain the connected components of a dynamic planar graph in O(logn) time per operation. We also show that any algorithm will need Ω(log n) amortized time per operation, given a set of machine operations that is fairly general.

AB - We give an efficient algorithm for maintaining a minimum spanning forest of a plane graph subject to on-line modifications. The modifications supported include changes in the edge weights and insertion and deletion of edges and vertices which are consistent with the given embedding. 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 algorithm runs in O(log n) time per operation and O(n) space. The algorithm can be used to maintain the connected components of a dynamic planar graph in O(logn) time per operation. We also show that any algorithm will need Ω(log n) amortized time per operation, given a set of machine operations that is fairly general.

UR - http://www.scopus.com/inward/record.url?scp=38249015356&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249015356&partnerID=8YFLogxK

U2 - 10.1016/0196-6774(92)90004-V

DO - 10.1016/0196-6774(92)90004-V

M3 - Article

AN - SCOPUS:38249015356

VL - 13

SP - 33

EP - 54

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 1

ER -