Fully-dynamic planarity testing in polylogarithmic time

Jacob Holm; Eva Rotenberg

doi:10.1145/3357713.3384249

Fully-dynamic planarity testing in polylogarithmic time

Jacob Holm, Eva Rotenberg

Algorithms and Complexity

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

15 Citationer (Scopus)

13 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(log³ 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	https://doi.org/10.1145/3357713.3384249
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/Område	USA
By	Chicago
Periode	22/06/2020 → 26/06/2020
Sponsor	ACM Special Interest Group on Algorithms and Computation Theory (SIGACT)

Adgang til dokumentet

10.1145/3357713.3384249

FulltextAccepteret manuskript, 832 KBLicens: CC BY

Citationsformater

Fully-dynamic planarity testing in polylogarithmic time. / Holm, Jacob; Rotenberg, Eva.
STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. red. / Konstantin Makarychev; Yury Makarychev; Madhur Tulsiani; Gautam Kamath; Julia Chuzhoy. Association for Computing Machinery, 2020. s. 167-180.

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Holm, J & Rotenberg, E 2020, Fully-dynamic planarity testing in polylogarithmic time. i K Makarychev, Y Makarychev, M Tulsiani, G Kamath & J Chuzhoy (red), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, s. 167-180, 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, USA, 22/06/2020. https://doi.org/10.1145/3357713.3384249

@inproceedings{8c747694c3704f2f843c42410486eaed,

title = "Fully-dynamic planarity testing in polylogarithmic time",

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.",

keywords = "Deterministic amortized upper bound, Dynamic graphs, Planarity",

author = "Jacob Holm and Eva Rotenberg",

year = "2020",

doi = "10.1145/3357713.3384249",

language = "English",

pages = "167--180",

editor = "Konstantin Makarychev and Yury Makarychev and Madhur Tulsiani and Gautam Kamath and Julia Chuzhoy",

booktitle = "STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

note = "52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 ; Conference date: 22-06-2020 Through 26-06-2020",

}

TY - GEN

T1 - Fully-dynamic planarity testing in polylogarithmic time

AU - Holm, Jacob

AU - Rotenberg, Eva

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Deterministic amortized upper bound

KW - Dynamic graphs

KW - Planarity

U2 - 10.1145/3357713.3384249

DO - 10.1145/3357713.3384249

M3 - Article in proceedings

AN - SCOPUS:85086766769

SP - 167

EP - 180

BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Makarychev, Konstantin

A2 - Makarychev, Yury

A2 - Tulsiani, Madhur

A2 - Kamath, Gautam

A2 - Chuzhoy, Julia

PB - Association for Computing Machinery

T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020

Y2 - 22 June 2020 through 26 June 2020

ER -