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 for this work

Algorithms and Complexity

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › 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.

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	https://doi.org/10.4230/LIPIcs.SoCG.2023.40
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
Country/Territory	United States
City	Dallas
Period	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.

Keywords

connectivity
dynamic graphs
planarity

Access to Document

10.4230/LIPIcs.SoCG.2023.40Licence: CC BY

FulltextFinal published version, 1.19 MBLicence: CC BY

Cite this

Holm, J., van der Hoog, I., & Rotenberg, E. (2023). Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. In E. W. Chambers, & J. Gudmundsson (Eds.), 39th International Symposium on Computational Geometry, SoCG 2023 [40] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 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. ed. / Erin W. Chambers; Joachim Gudmundsson. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 40 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 258).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Holm, J, van der Hoog, I & Rotenberg, E 2023, Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. in EW Chambers & J Gudmundsson (eds), 39th International Symposium on Computational Geometry, SoCG 2023., 40, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 258, 39th International Symposium on Computational Geometry, SoCG 2023, Dallas, United States, 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. In Chambers EW, Gudmundsson J, editors, 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, Vol. 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. editor / Erin W. Chambers ; Joachim Gudmundsson. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 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 -