@inproceedings{3ec2ea61bde947f8b53f70aad0726520,
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(gn) time per update.",
keywords = "Deterministic amortized upper bound, Dynamic graphs, Planarity",
author = "Jacob Holm and Eva Rotenberg",
year = "2020",
month = jun,
day = "8",
doi = "10.1145/3357713.3384249",
language = "English",
series = "Proceedings of the Annual Acm Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "167--180",
editor = "Konstantin Makarychev and Yury Makarychev and Madhur Tulsiani and Gautam Kamath and Julia Chuzhoy",
booktitle = "Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing",
address = "United States",
note = "52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 ; Conference date: 22-06-2020 Through 26-06-2020",
}