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

Jacob Holm; Ivor van der Hoog; Eva Rotenberg

doi:10.4230/LIPIcs.SoCG.2023.40

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

Jacob Holm^*, Ivor van der Hoog, Eva Rotenberg

^*Corresponding author af dette arbejde

Algorithms and Complexity

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

10 Downloads (Pure)

Abstract

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(log² 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	https://doi.org/10.4230/LIPIcs.SoCG.2023.40
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/Område	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.

Adgang til dokumentet

10.4230/LIPIcs.SoCG.2023.40Licens: CC BY

FulltextForlagets udgivne version, 1,19 MBLicens: CC BY

Citationsformater

Holm, J., van der Hoog, I., & Rotenberg, E. (2023). Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. I E. W. Chambers, & J. Gudmundsson (red.), 39th International Symposium on Computational Geometry, SoCG 2023 [40] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Bind 258 https://doi.org/10.4230/LIPIcs.SoCG.2023.40

Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. / Holm, Jacob; van der Hoog, Ivor; Rotenberg, Eva.

39th International Symposium on Computational Geometry, SoCG 2023. red. / Erin W. Chambers; Joachim Gudmundsson. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 40 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 258).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Holm, J, van der Hoog, I & Rotenberg, E 2023, Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. i EW Chambers & J Gudmundsson (red), 39th International Symposium on Computational Geometry, SoCG 2023., 40, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, bind 258, 39th International Symposium on Computational Geometry, SoCG 2023, Dallas, USA, 12/06/2023. https://doi.org/10.4230/LIPIcs.SoCG.2023.40

Holm J, van der Hoog I, Rotenberg E. Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. I Chambers EW, Gudmundsson J, red., 39th International Symposium on Computational Geometry, SoCG 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 40. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 258). https://doi.org/10.4230/LIPIcs.SoCG.2023.40

Holm, Jacob ; van der Hoog, Ivor ; Rotenberg, Eva. / Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. 39th International Symposium on Computational Geometry, SoCG 2023. red. / Erin W. Chambers ; Joachim Gudmundsson. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 258).

@inproceedings{c911c64c9a2345ec9781570cd0f82267,

title = "Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings",

abstract = "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.",

keywords = "connectivity, dynamic graphs, planarity",

author = "Jacob Holm and {van der Hoog}, Ivor and Eva Rotenberg",

note = "Publisher Copyright: {\textcopyright} Jacob Holm, Ivor van der Hoog, and Eva Rotenberg; licensed under Creative Commons License CC-BY 4.0.; 39th International Symposium on Computational Geometry, SoCG 2023 ; Conference date: 12-06-2023 Through 15-06-2023",

year = "2023",

doi = "10.4230/LIPIcs.SoCG.2023.40",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Chambers, {Erin W.} and Joachim Gudmundsson",

booktitle = "39th International Symposium on Computational Geometry, SoCG 2023",

}

TY - GEN

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

AU - Holm, Jacob

AU - van der Hoog, Ivor

AU - Rotenberg, Eva

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

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - connectivity

KW - dynamic graphs

KW - planarity

U2 - 10.4230/LIPIcs.SoCG.2023.40

DO - 10.4230/LIPIcs.SoCG.2023.40

M3 - Article in proceedings

AN - SCOPUS:85163488881

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 39th International Symposium on Computational Geometry, SoCG 2023

A2 - Chambers, Erin W.

A2 - Gudmundsson, Joachim

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 39th International Symposium on Computational Geometry, SoCG 2023

Y2 - 12 June 2023 through 15 June 2023

ER -