Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language | English |
---|---|
Title of host publication | 39th International Symposium on Computational Geometry, SoCG 2023 |
Editors | Erin W. Chambers, Joachim Gudmundsson |
Number of pages | 18 |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2023 |
Article number | 40 |
ISBN (Electronic) | 9783959772730 |
DOIs | |
Publication status | Published - 2023 |
Event | 39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, United States Duration: 12 Jun 2023 → 15 Jun 2023 |
Conference
Conference | 39th International Symposium on Computational Geometry, SoCG 2023 |
---|---|
Land | United States |
By | Dallas |
Periode | 12/06/2023 → 15/06/2023 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 258 |
ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:
© Jacob Holm, Ivor van der Hoog, and Eva Rotenberg; licensed under Creative Commons License CC-BY 4.0.
- connectivity, dynamic graphs, planarity
Research areas
ID: 383441428