10
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?