Are there any online algorithms for planarity testing?

Question

I know that planarity testing can be done in O(v) (equivalently O(e), since planar graphs have O(v) edges) time.

I wonder if it can be done online in O(1) amortized time as each edge is added (still O(e) time overall).

In other words, in a database table representing edges of a graph and subject to a constraint that the represented graph is planar, how much time must the DBMS responsible for managing the constraint take to validate each proposed insertion? (For simplification, assume that there are no deletions.) Must it re-run one of the O(v) planarity testing algorithms to test each proposed insertion or group of insertions?

Answer 1

After some more research it appears that the answer is "yes", there are online algorithms, but "no" there are none with O(1) amortized running time.

Here's a 1999 paper in the Journal of the ACM, Fully dynamic planarity testing with applications, in which the authors wrote:

In particular, we consider the following three 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(n^2/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.

I also found the abstract of a 1989 paper, Incremental planarity testing claiming an O(log n) bound for edge insertion, but I'm not sure if their technique covers deletion as well.

The 1999 paper also refers to an O(inverse-ackermann(total-operations, n)) algorithm for the case of no deletions, discussed in a 1992 paper, Fast incremental planarity testing, but CiteSeer is down at the moment, so I'll read the details later.

Deletion being useful to my application, and having access to the J. ACM paper, I'm going to read further on the amortized O(n^2/3) strategy.