Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Final published version, 1.19 MB, PDF document

We study dynamic planar graphs with n vertices, subject to edge deletion, edge contraction, edge insertion across a face, and the splitting of a vertex in specified corners. We dynamically maintain a combinatorial embedding of such a planar graph, subject to connectivity and 2-vertex-connectivity (biconnectivity) queries between pairs of vertices. Whenever a query pair is connected and not biconnected, we find the first and last cutvertex separating them. Additionally, we allow local changes to the embedding by flipping the embedding of a subgraph that is connected by at most two vertices to the rest of the graph. We support all queries and updates in deterministic, worst-case, O(log2 n) time, using an O(n)-sized data structure.

Original languageEnglish
Title of host publication39th International Symposium on Computational Geometry, SoCG 2023
EditorsErin W. Chambers, Joachim Gudmundsson
Number of pages18
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date2023
Article number40
ISBN (Electronic)9783959772730
DOIs
Publication statusPublished - 2023
Event39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, United States
Duration: 12 Jun 202315 Jun 2023

Conference

Conference39th International Symposium on Computational Geometry, SoCG 2023
LandUnited States
ByDallas
Periode12/06/202315/06/2023
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume258
ISSN1868-8969

Bibliographical note

Publisher Copyright:
© Jacob Holm, Ivor van der Hoog, and Eva Rotenberg; licensed under Creative Commons License CC-BY 4.0.

    Research areas

  • connectivity, dynamic graphs, planarity

ID: 383441428