2019/11/08 by Jacob Holm, Holm, Jacob, Eva Rotenberg +1 · 1 voice
#cs.DS
paper · pdf · doi:10.48550/arxiv.1911.03449
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(log3 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.