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

University of Copenhagen

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

31 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	Proceedings of the 39th International Symposium on Computational Geometry, SoCG 2023
Number of pages	18
Volume	258
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date	2023
Article number	40
ISBN (Electronic)	978-3-95977-273-0
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

Keywords

Connectivity
Dynamic graphs
Planarity

Access to Document

10.4230/LIPIcs.SoCG.2023.40Licence: CC BY

FulltextFinal published version, 1.19 MBLicence: CC BY

OpenUrl availability

Full text

Cite this

@inproceedings{e966b06367bc4eb4a2ddc7889d16f6a3,

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, SoCG ; Conference date: 12-06-2023 Through 15-06-2023",

year = "2023",

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

language = "English",

volume = "258",

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

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

}

Holm, J, van der Hoog, I & Rotenberg, E 2023, Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. in Proceedings of the 39th International Symposium on Computational Geometry, SoCG 2023. vol. 258, 40, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 39th International Symposium on Computational Geometry, SoCG 2023, Dallas, United States, 12/06/2023. 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.
Proceedings of the 39th International Symposium on Computational Geometry, SoCG 2023. Vol. 258 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 40.

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

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

VL - 258

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

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 -

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

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this