An apprentice that discovers hypertext links

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