Fully-dynamic planarity testing in polylogarithmic time

Given a dynamic graph subject to insertions and deletions of edges, a natural question is whether the graph presently admits a planar embedding. We give a deterministic fully-dynamic algorithm for general graphs, running in amortized O (log 3 n ) time per edge insertion or deletion, that maintains a bit indicating whether or not the graph is presently planar. This is an exponential improvement over the previous best algorithm [Eppstein, Galil, Italiano, Spencer, 1996] which spends amortized O (√ n ) time per update.

Authors

• Jacob Holm
• Eva Rotenberg

Keywords

• deterministic amortized upper bound
• dynamic graphs
• planarity