ONLINE PLANARITY TESTING

The on-line planarity-testing problem consists of performing the follo wing operations on a planar graph G: (i) testing if a new edge can be added to G so that the resulting graph is itself planar; (ii) adding v ertices and edges such that planarity is preserved. An efficient techn ique for online planarity testing of a graph is presented that uses O( n) space and supports tests and insertions of vertices and edges in O( log n) time, where n is the current number of vertices of G. The bound s for tests and vertex insertions are worst-case and the bound for edg e insertions is amortized. We also present other applications of this technique to dynamic algorithms for planar graphs.