Fully-dynamic planarity testing in polylogarithmic time
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Accepteret manuskript, 832 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing |
Redaktører | Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy |
Forlag | Association for Computing Machinery |
Publikationsdato | 2020 |
Sider | 167-180 |
ISBN (Elektronisk) | 9781450369794 |
DOI | |
Status | Udgivet - 2020 |
Begivenhed | 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, USA Varighed: 22 jun. 2020 → 26 jun. 2020 |
Konference
Konference | 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 |
---|---|
Land | USA |
By | Chicago |
Periode | 22/06/2020 → 26/06/2020 |
Sponsor | ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) |
ID: 246825065