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(√n) time per update.
Original language | English |
---|---|
Title of host publication | STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing |
Editors | Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy |
Publisher | Association for Computing Machinery |
Publication date | 2020 |
Pages | 167-180 |
ISBN (Electronic) | 9781450369794 |
DOIs | |
Publication status | Published - 2020 |
Event | 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States Duration: 22 Jun 2020 → 26 Jun 2020 |
Conference
Conference | 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 |
---|---|
Country/Territory | United States |
City | Chicago |
Period | 22/06/2020 → 26/06/2020 |
Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) |
Keywords
- Deterministic amortized upper bound
- Dynamic graphs
- Planarity