Maintenance of a minimum spanning forest in a dynamic plane graph

DOI10.1016/0196-6774(92)90004-VzbMath0751.05081WikidataQ61609652 ScholiaQ61609652MaRDI QIDQ3990614

Roberto Tamassia, David Eppstein, Giuseppe F. Italiano, Mordechai M. Yung, Jeffery Westbrook, Robert Endre Tarjan

Publication date: 28 June 1992

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(92)90004-v

zbMATH Keywords

plane graphs; minimum spanning forest; dynamic trees

Mathematics Subject Classification ID

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Maintaining spanning trees of small diameter, The Painter’s Problem: Covering a Grid with Colored Connected Polygons, A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING, Unnamed Item, Dynamic 2- and 3-connectivity on planar graphs, Lower bounds for dynamic algorithms, Decremental SPQR-trees for Planar Graphs, Efficient Extraction of Multiple Kuratowski Subdivisions, FINDING PLANAR REGIONS IN A TERRAIN – IN PRACTICE AND WITH A GUARANTEE, Minimum-weight spanning tree algorithms. A survey and empirical study, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., A uniform self-stabilizing minimum diameter spanning tree algorithm, Fully Dynamic Transitive Closure in plane dags with one source and one sink, Dynamic connectivity in disk graphs, On-line convex planarity testing, Dynamic connectivity in digital images, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, Efficient authenticated data structures for graph connectivity and geometric search problems, Planar and grid graph reachability problems, Efficient algorithms for computing Reeb graphs, Maintaining dynamic minimum spanning trees: an experimental study, A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs, Dynamic expression trees, Optimal decremental connectivity in planar graphs, Dynamic planar embeddings of dynamic graphs, Incremental convex planarity testing, Decremental 2- and 3-connectivity on planar graphs, Constant-time dynamic weight approximation for minimum spanning forest, Single-source shortest paths and strong connectivity in dynamic planar graphs, Competitive graph searches, Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning, Dynamic Trees and Dynamic Point Location