Fully-dynamic planarity testing in polylogarithmic time

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


  • Fulltext

    Accepted author manuscript, 832 KB, PDF document

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.

Original languageEnglish
Title of host publicationSTOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
EditorsKonstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
PublisherAssociation for Computing Machinery
Publication date2020
ISBN (Electronic)9781450369794
Publication statusPublished - 2020
Event52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States
Duration: 22 Jun 202026 Jun 2020


Conference52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
LandUnited States
SponsorACM Special Interest Group on Algorithms and Computation Theory (SIGACT)

    Research areas

  • Deterministic amortized upper bound, Dynamic graphs, Planarity

ID: 246825065