Fully-dynamic planarity testing in polylogarithmic time

DOI10.1145/3357713.3384249OpenAlexW3035122908MaRDI QIDQ5144906

Jacob Holm, Eva Rotenberg

Publication date: 19 January 2021

Published in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1911.03449

zbMATH Keywords

planaritydynamic graphsdeterministic amortized upper bound

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (5)

Atomic Embeddability, Clustered Planarity, and Thickenability ⋮ Maintaining triconnected components under node expansion ⋮ Synchronized Planarity with Applications to Constrained Planarity Problems ⋮ Work-sensitive dynamic complexity of formal languages ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs

This page was built for publication: Fully-dynamic planarity testing in polylogarithmic time