  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(\sqrt{n})$ time per update.
