Fully dynamic planarity testing in planar embedded graphs

Giuseppe F. Italiano, Johannes A. La Poutré, and Monika H. Rauch
Proc. 1st Eur. Symp. Algorithms (ESA 1993), Lecture Notes in Computer Science 726, Thomas Lengauer, ed., Springer-Verlag, Sep 1993, pp. 212–223
http://www.cs.cornell.edu/Info/People/mhr/papers/planarity-testing.ps

Cites:

• Maintenance of a minimum spanning forest in a dynamic planar graph
• Sparsification — A technique for speeding up dynamic graph algorithms
• Separator based sparsification for dynamic planar graph algorithms