Separator based sparsification for dynamic planar graph algorithms

DOI10.1145/167088.167159zbMath1310.05197OpenAlexW2022827580MaRDI QIDQ5248488

Giuseppe F. Italiano, Thomas H. Spencer, David Eppstein, Zvi Galil

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167159

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (17)

Data structures for two-edge connectivity in planar graphs ⋮ Dynamic connectivity in digital images ⋮ Using sparsification for parametric minimum spanning tree problems ⋮ Fully dynamic biconnectivity in graphs ⋮ Maintaining minimum spanning trees in dynamic graphs ⋮ Certificates and fast algorithms for biconnectivity in fully-dynamic graphs ⋮ Fully Dynamic Transitive Closure in plane dags with one source and one sink ⋮ A dynamic algorithm for line graph recognition ⋮ A dynamic topological sort algorithm for directed acyclic graphs ⋮ Output-sensitive reporting of disjoint paths (extended abstract) ⋮ On-line convex planarity testing ⋮ Analysis and Experimental Study of Heuristics for Job Scheduling Reoptimization Problems ⋮ Dynamic Distance Hereditary Graphs Using Split Decomposition ⋮ Dynamic and static algorithms for optimal placement of resources in a tree ⋮ Discovering recurring activity in temporal networks ⋮ Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning ⋮ Finding the k Shortest Paths

This page was built for publication: Separator based sparsification for dynamic planar graph algorithms