Incremental planarity testing
Giuseppe Di Battista, Roberto Tamassia · 1989
The incremental planarity testing problem consists of performing the following operations on a planar graph G with n vertices: (1) testing whether a new edge can be added to G so that the resulting graph is itself planar; (2) adding vertices and edges such that planarity is preserved. An efficient technique for incremental planarity testing that uses O(n) space and supports tests and insertion of vertices and edges in O(log n) time is presented. The bounds for queries and vertex insertions are worst case, and the bound for edge insertions is amortized.>