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.

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

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	Leibniz International Proceedings in Informatics
Number of pages	18
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Publication date	6 Sept 2023
Pages	40:1-40:18
Article number	40
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2023.40
Publication status	Published - 6 Sept 2023
Externally published	Yes
Event	Symposium on Computational Geometry - United States , Dallas, United States Duration: 12 Jun 2023 → 13 Jun 2023 Conference number: 39 https://apps.utdallas.edu/SOCG23/socg.html

Conference

Conference	Symposium on Computational Geometry
Number	39
Location	United States
Country/Territory	United States
City	Dallas
Period	12/06/2023 → 13/06/2023
Internet address	https://apps.utdallas.edu/SOCG23/socg.html

Keywords

Dynamic graphs
Planarity
Connectivity

Access to Document

10.4230/LIPIcs.SoCG.2023.40Licence: CC BY

Cite this

@inproceedings{902fd0f299fa4c3d8865d693ee1cd4d0,

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(log² n) time, using an O(n)-sized data structure.",

keywords = "Dynamic graphs, Planarity, Connectivity",

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

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.; Symposium on Computational Geometry, SoCG ; Conference date: 12-06-2023 Through 13-06-2023",

year = "2023",

month = sep,

day = "6",

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

language = "English",

pages = "40:1--40:18",

booktitle = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH",

url = "https://apps.utdallas.edu/SOCG23/socg.html",

}

Holm, J, van der Hoog, I & Rotenberg, E 2023, Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings. in Leibniz International Proceedings in Informatics., 40, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, pp. 40:1-40:18, Symposium on Computational Geometry, Dallas, Texas, 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.
Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2023. p. 40:1-40:18 40.

Research output: Conference Article in Proceeding or Book/Report chapter › 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 - Conference code: 39

PY - 2023/9/6

Y1 - 2023/9/6

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(log² 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(log² n) time, using an O(n)-sized data structure.

KW - Dynamic graphs

KW - Planarity

KW - Connectivity

U2 - 10.4230/LIPIcs.SoCG.2023.40

DO - 10.4230/LIPIcs.SoCG.2023.40

M3 - Article in proceedings

SP - 40:1-40:18

BT - Leibniz International Proceedings in Informatics

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH

T2 - Symposium on Computational Geometry

Y2 - 12 June 2023 through 13 June 2023

ER -

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

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this