Fully dynamic planarity testing with applications

Zvi Galil, Giuseppe F. Italiano, and Neil Sarnak
J. ACM 46(1):28–91, Jan 1999
http://www.acm.org/pubs/citations/journals/jacm/1999-46-1/p28-galil/

Cites:

• Sparsification — A technique for speeding up dynamic graph algorithms
• Separator based sparsification I: planarity testing and minimum spanning trees
• Separator based sparsification II: edge and vertex connectivity
• Maintenance of a minimum spanning forest in a dynamic planar graph