Publication
STOC 1992
Conference paper

Fully dynamic planarity testing

Download paper

Abstract

The fully dynamic planarity testing problem consists of performing an arbitrary sequence of the following three kinds of operations on a planar graph G: (i) insert an edge if the resultant graph remains planar; (ii) delete an edge; and (iii) test whether an edge could be added to the graph without violating planarity. We show how to support each of the above operations in O(n2/3) time, where n is the number of vertices in the graph. The bound for tests and deletions is worst-case, while the bound for insertions is amortized. This is the first algorithm for this problem with sub-linear running time. The same data structure has further applications in maintaining the biconnected and triconnected components of a dynamic planar graph.

Date

Publication

STOC 1992

Authors

Resources

Share