Maintenance of a minimum spanning forest in a dynamic planar graph

David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert E. Tarjan, Jeffery R. Westbrook, and Moti Yung
J. Algorithms 13(1):33–54, Mar 1992
J. Algorithms 15:173, 1993
Proc. 1st Symp. Discrete Algorithms, ACM and SIAM, Jan 1990, pp. 1–11
Tech. report 243-90, Princeton Univ., Dept. of Computer Science, 1990
Mathematical Reviews 94b:68039
Mathematical Reviews 93a:68027

Cited by:

• Dynamic data structures for series parallel digraphs
• Lower bounds for dynamic algorithms
• Faster approximation algorithms for the rectilinear Steiner problem
• Approaching the $5/4$-approximation for rectilinear Steiner trees
• The dynamic predicate stashing copy problem
• Bounded incremental computation
• Decremental 2- and 3-connectivity on planar graphs
• Fully dynamic algorithms for 2-edge-connectivity
• Maintaining the 3-edge connected components of a graph online
• Incremental algorithms for minimal length paths
• Dynamic algorithms for shortest paths in planar graphs
• Maintaining biconnected components of dynamic planar graphs
• Fully dynamic planarity testing
• Dynamic expression trees
• Combine and conquer: a general technique for dynamic algorithms
• On-line graph algorithms with SPQR-trees
• Dynamic trees and dynamic point location
• Dynamic ray shooting and shortest paths via balanced geodesic triangulations
• A framework for dynamic graph drawing
• Dynamic graph algorithms and data structures
• Maintenance of triconnected components of graphs
• Alpha-algorithms for incremental planarity testing
• Biased finger trees and three-dimensional layers of maxima
• How to treat delete requests in semi-online problems
• Fully dynamic planarity testing in planar embedded graphs
• Fully dynamic 2-edge-connectivity in planar graphs
• Fully Dynamic Graph Algorithms and their Data Structures
• Fully dynamic biconnectivity in graphs
• Improved data structures for fully dynamic biconnectivity
• Fully dynamic cycle-equivalence in graphs
• A new class of iterative Steiner tree heuristics with good performance
• A data structure for dynamically maintaining rooted trees
• Ambivalent data structures for dynamic 2-edge-connectivity and $k$ smallest spanning trees
• A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Bipartite graphs, upward drawings, and planarity
• On-line convex planarity testing
• Fully dynamic transitive closure in plane dags with one source and one sink
• Planar separators and parallel polygon triangulation
• On-line planar graph embedding
• On-line planarity testing
• Dynamic data structures for graphs
• Implementation of the dynamic connectivity algorithm by Monika Rauch Henzinger and Valerie King
• Experimental analysis of dynamic minimum spanning tree algorithms
• Combine and Conquer
• Dynamically switching vertices in planar graphs
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• Average case analysis of fully dynamic reachability for directed graphs
• Data structures for topological and geometric operations on networks
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
• Maintaining spanning trees of small diameter
• Maintaining regular properties dynamically in $k$-terminal graphs
• Lower bounds for fully dynamic connectivity problems in graphs
• Kinetic connectivity of rectangles
• Fully dynamic planarity testing with applications
• Geometric Data Structures and Applications
• Searching constant width mazes captures the AC$^0$-hierarchy
• Maintenance of 2- and 3-edge-connected components of graphs II
• Dynamic graph algorithms{}
• Cell probe complexity — a survey
• Efficiency by incrementalization: an introduction
• Minimum-weight spanning tree algorithms – A survey and empirical study
• A case study in algorithm engineering for geometric computing
• Incremental convex planarity testing
• Authenticated data structures for graph and geometric searching
• Maintaining dynamic minimum spanning trees: An experimental study
• Fully dynamic algorithms for bounded genus graphs
• Lower bounds for dynamic connectivity
• Kinetic Maintenance of Proximity Structures
• Maintaining Consistency and Behavior of Object-Oriented Systems During Evolution
• Logarithmic lower bounds in the cell-probe model
• Multiple-source shortest paths in planar graphs
• An $O(n\log n)$ algorithm for maximum $st$-flow in a directed planar graph