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

Department of Applied Mathematics and Computer Science

University of Copenhagen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

91 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(gn) time per update.

Original language	English
Title of host publication	Proceedings of the 52^nd Annual ACM SIGACT Symposium on Theory of Computing
Editors	Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
Publisher	Association for Computing Machinery
Publication date	8 Jun 2020
Pages	167-180
ISBN (Electronic)	9781450369794
DOIs	https://doi.org/10.1145/3357713.3384249
Publication status	Published - 8 Jun 2020
Event	52nd Annual ACM SIGACT Symposium on Theory of Computing - Chicago, United States Duration: 22 Jun 2020 → 26 Jun 2020 Conference number: 52

Conference

Conference	52nd Annual ACM SIGACT Symposium on Theory of Computing
Number	52
Country/Territory	United States
City	Chicago
Period	22/06/2020 → 26/06/2020
Sponsor	Association for Computing Machinery

Keywords

Deterministic amortized upper bound
Dynamic graphs
Planarity

Access to Document

10.1145/3357713.3384249

FulltextAccepted author manuscript, 832 KB

OpenUrl availability

Full text

Cite this

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

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

publisher = "Association for Computing Machinery",

address = "United States",

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

}

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

Fully-dynamic planarity testing in polylogarithmic time. / Holm, Jacob; Rotenberg, Eva.
Proceedings of the 52^nd 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

TY - GEN

T1 - Fully-dynamic planarity testing in polylogarithmic time

AU - Holm, Jacob

AU - Rotenberg, Eva

N1 - Conference code: 52

PY - 2020/6/8

Y1 - 2020/6/8

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(gn) 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(gn) 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 - 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

Y2 - 22 June 2020 through 26 June 2020

ER -

Fully-dynamic planarity testing in polylogarithmic time

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this