Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 1,19 MB, PDF-dokument
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.
| Originalsprog | Engelsk |
|---|---|
| Titel | 39th International Symposium on Computational Geometry, SoCG 2023 |
| Redaktører | Erin W. Chambers, Joachim Gudmundsson |
| Antal sider | 18 |
| Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Publikationsdato | 2023 |
| Artikelnummer | 40 |
| ISBN (Elektronisk) | 9783959772730 |
| DOI | |
| Status | Udgivet - 2023 |
| Begivenhed | 39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, USA Varighed: 12 jun. 2023 → 15 jun. 2023 |
Konference
| Konference | 39th International Symposium on Computational Geometry, SoCG 2023 |
|---|---|
| Land | USA |
| By | Dallas |
| Periode | 12/06/2023 → 15/06/2023 |
| Navn | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Vol/bind | 258 |
| ISSN | 1868-8969 |
Bibliografisk note
Funding Information:
Funding Ivor van der Hoog and Eva Rotenberg: Partially supported by Independent Research Fund Denmark grants 2020-2023 (9131-00044B) “Dynamic Network Analysis”. Jacob Holm: Partially supported by the VILLUM Foundation grant 16582, “BARC”. Ivor van der Hoog: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987.
Funding Information:
Ivor van der Hoog and Eva Rotenberg: Partially supported by Independent Research Fund Denmark grants 2020-2023 (9131-00044B) “Dynamic Network Analysis”. Jacob Holm: Partially supported by the VILLUM Foundation grant 16582, “BARC”. Ivor van der Hoog: This project has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987.
Publisher Copyright:
© Jacob Holm, Ivor van der Hoog, and Eva Rotenberg; licensed under Creative Commons License CC-BY 4.0.
ID: 383441428