Fully dynamic planarity testing (extended abstract)
Zvi Galil, Giuseppe Francesco Italiano, Neil Sarnak · 1992
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 i resultant graph remains planar; (ii delete an edge; and (iii) test whether an edge could be ad ed to the graph without violating planarity.We show how to support each of the above operations in 0(TZ2/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 haa further applications in maintaining the biconnected and triconnected components of a dynamic planar graph.