Dynamically switching vertices in planar graphs

Daniele Frigioni and Giuseppe F. Italiano
Algorithmica 28(1):76–103, 2000
Proc. 5th Eur. Symp. Algorithms (ESA 1997), Lecture Notes in Computer Science 1284, Rainer Ernst Burkard and Gerhard J. Woeginger, ed., Springer-Verlag, Sep 1997, pp. 186–199
http://link.springer-ny.com/link/service/journals/00453/contents/00/10032/

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