Fully-dynamic planarity testing in polylogarithmic time

DOI10.1145/3357713.3384249MaRDI QIDQ5144906zbMATH OpenOpenAlexFDO

Authors 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

deterministic amortized upper bounddynamic graphsplanarity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Testing Full Outer-2-planarity in Linear Time
• A linear-time algorithm for testing full outer-2-planarity
• Fully dynamic planarity testing with applications
• scientific article; zbMATH DE number 1500509
• The complexity of planarity testing
• scientific article; zbMATH DE number 1377359
• Fast incremental planarity testing
• A linear-time algorithm for testing outer-1-planarity
• A linear-time algorithm for testing outer-1-planarity

Cited in

(12)

• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Work-sensitive dynamic complexity of formal languages
• Testing Full Outer-2-planarity in Linear Time
• A direct linear-time planarity test for unflippable modules
• Atomic Embeddability, Clustered Planarity, and Thickenability
• Fast incremental planarity testing
• Maintaining triconnected components under node expansion
• Synchronized Planarity with Applications to Constrained Planarity Problems
• Improved dynamic colouring of sparse graphs
• Maintaining triconnected components under node expansion
• Simple dynamic spanners with near-optimal recourse against an adaptive adversary
• Dynamic embeddings of dynamic single-source upward planar graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144906)