Separator based sparsification for dynamic planar graph algorithms
DOI10.1145/167088.167159zbMATH Open1310.05197OpenAlexW2022827580MaRDI QIDQ5248488FDOQ5248488
Authors: David Eppstein, Giuseppe F. Italiano, Thomas H. Spencer, 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
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cited In (17)
- Dynamic and static algorithms for optimal placement of resources in a tree
- Output-sensitive reporting of disjoint paths (extended abstract)
- Dynamic Distance Hereditary Graphs Using Split Decomposition
- Discovering recurring activity in temporal networks
- Dynamic connectivity in digital images
- Fully dynamic biconnectivity in graphs
- A dynamic algorithm for line graph recognition
- On-line convex planarity testing
- Data structures for two-edge connectivity in planar graphs
- Finding the k Shortest Paths
- Fully Dynamic Transitive Closure in plane dags with one source and one sink
- Maintaining minimum spanning trees in dynamic graphs
- Analysis and Experimental Study of Heuristics for Job Scheduling Reoptimization Problems
- A dynamic topological sort algorithm for directed acyclic graphs
- Using sparsification for parametric minimum spanning tree problems
- Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
- Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
This page was built for publication: Separator based sparsification for dynamic planar graph algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5248488)
