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

}