Separator based sparsification for dynamic planar graph algorithms

David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer
Proc. 25th Symp. Theory of Computing, ACM, May 1993, pp. 208–217
http://www.acm.org/pubs/citations/proceedings/stoc/167088/p208-eppstein/

Cited by:

• Alpha-algorithms for incremental planarity testing
• A fully dynamic data structure for reachability in planar digraphs
• Fast algorithms for dynamic 2-connectivity with backtracking
• Fully dynamic planarity testing in planar embedded graphs
• Improved data structures for fully dynamic biconnectivity
• Fully dynamic cycle-equivalence in graphs
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
• Data structures for two-edge connectivity in planar graphs
• Algorithms for drawing graphs: an annotated bibliography
• On-line convex planarity testing
• Fully dynamic biconnectivity and transitive closure
• Fully dynamic transitive closure in plane dags with one source and one sink
• Planar separators and parallel polygon triangulation
• An empirical study of dynamic graph algorithms
• A dynamic algorithm for line graph recognition
• Output-sensitive reporting of disjoint paths
• On-line planar graph embedding
• Implementation of the dynamic connectivity algorithm by Monika Rauch Henzinger and Valerie King
• Experimental analysis of dynamic minimum spanning tree algorithms
• Dyn-FO: a parallel, dynamic complexity class
• Dynamic and static algorithms for optimal placement of resources in a tree
• Lower bounds for fully dynamic connectivity problems in graphs
• There Are Parallel and Dynamic Shortest-Path Algorithms for Sparse Graphs
• Maintenance of 2- and 3-edge-connected components of graphs II
• Dynamic graph algorithms{}
• Maintaining dynamic minimum spanning trees: An experimental study