Fully-dynamic planarity testing in polylogarithmic time

Jacob Holm, Eva Rotenberg

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

39 Downloads (Pure)

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(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(gn) time per update.

Original languageEnglish
Title of host publicationProceedings 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 date8 Jun 2020
Pages167-180
ISBN (Electronic)9781450369794
DOIs
Publication statusPublished - 8 Jun 2020
Event52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States
Duration: 22 Jun 202026 Jun 2020

Conference

Conference52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
CountryUnited States
CityChicago
Period22/06/202026/06/2020
SponsorAssociation for Computing Machinery
SeriesProceedings of the Annual Acm Symposium on Theory of Computing
ISSN0737-8017

Keywords

  • Deterministic amortized upper bound
  • Dynamic graphs
  • Planarity

Fingerprint Dive into the research topics of 'Fully-dynamic planarity testing in polylogarithmic time'. Together they form a unique fingerprint.

Cite this