2020/06/07 by Jacob Holm, Eva Rotenberg · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Combinatorics #Planarity testing #Embedding #Amortized analysis #Mathematics #Graph #Discrete mathematics #Planar graph #Binary logarithm #Book embedding #Time complexity #Computer science #Algorithm #Pathwidth #Line graph #Data structure #Artificial intelligence
paper · doi:10.1145/3357713.3384249
openalex publication_date 2020/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.