Fully-dynamic Planarity Testing in Polylogarithmic Time
Jacob Holm, Eva Rotenberg
Abstract
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.
arXiv comments
Updated version of paper submitted to STOC'20. This version features a complete rewrite of section 4.4 (do-separation-flips). The new version fixes an overlooked case in the previous version (the two fundamental cycles we find do not necessarily share an edge) and contains a detailed case-by-case proof of correctness
Linked by 2 identifiable commenters in 2 comments across 2 threads, from Aug 2020 to May 2021. Found in 1 HN submission from Jul 2020 to Jul 2020. Open submission discussions.
Fully dynamic planarity testing in polylogarithmic time https://arxiv.org/abs/1911.03449 https://www.youtube.com/watch?v=1deOVlruc-o
monicView on HNParent context