Separator based sparsification I: planarity testing and minimum spanning trees

David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer
J. Computer & Systems Sciences 52(1):3–27, Feb 1996
Mathematical Reviews 97c:05052
http://dx.doi.org/10.1006/jcss.1996.0002

Cited by:

• Dynamically switching vertices in planar graphs
• Maintaining regular properties dynamically in $k$-terminal graphs
• Fully dynamic planarity testing with applications
• Implementation and experimental evaluation of graph connectivity algorithms using LEDA
• Multi-parameter minimum spanning trees
• An experimental study of dynamic algorithms for transitive closure
• Incremental convex planarity testing
• Decomposable multi-parameter matroid optimization problems
• Fully dynamic algorithms for bounded genus graphs