Standard
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. ed. / Konstantin Makarychev; Yury Makarychev; Madhur Tulsiani; Gautam Kamath; Julia Chuzhoy. Association for Computing Machinery, 2020. p. 167-180.
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Holm, J & Rotenberg, E 2020,
Fully-dynamic planarity testing in polylogarithmic time. in K Makarychev, Y Makarychev, M Tulsiani, G Kamath & J Chuzhoy (eds),
STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, pp. 167-180, 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, United States,
22/06/2020.
https://doi.org/10.1145/3357713.3384249
APA
Holm, J., & Rotenberg, E. (2020).
Fully-dynamic planarity testing in polylogarithmic time. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, & J. Chuzhoy (Eds.),
STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (pp. 167-180). Association for Computing Machinery.
https://doi.org/10.1145/3357713.3384249
Vancouver
Holm J, Rotenberg E.
Fully-dynamic planarity testing in polylogarithmic time. In Makarychev K, Makarychev Y, Tulsiani M, Kamath G, Chuzhoy J, editors, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2020. p. 167-180
https://doi.org/10.1145/3357713.3384249
Author
Holm, Jacob ; Rotenberg, Eva. / Fully-dynamic planarity testing in polylogarithmic time. STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. editor / Konstantin Makarychev ; Yury Makarychev ; Madhur Tulsiani ; Gautam Kamath ; Julia Chuzhoy. Association for Computing Machinery, 2020. pp. 167-180
Bibtex
@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",
}
RIS
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 -
