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.

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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.

Originalsprog	Engelsk
Titel	Leibniz International Proceedings in Informatics
Antal sider	18
Forlag	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Publikationsdato	6 sep. 2023
Sider	40:1-40:18
Artikelnummer	40
DOI	https://doi.org/10.4230/LIPIcs.SoCG.2023.40
Status	Udgivet - 6 sep. 2023
Udgivet eksternt	Ja
Begivenhed	Symposium on Computational Geometry - United States , Dallas, USA Varighed: 12 jun. 2023 → 13 jun. 2023 Konferencens nummer: 39 https://apps.utdallas.edu/SOCG23/socg.html

Konference

Konference	Symposium on Computational Geometry
Nummer	39
Lokation	United States
Land/Område	USA
By	Dallas
Periode	12/06/2023 → 13/06/2023
Internetadresse	https://apps.utdallas.edu/SOCG23/socg.html

Adgang til dokumentet

10.4230/LIPIcs.SoCG.2023.40Licens: CC BY

Citationsformater

@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. i Leibniz International Proceedings in Informatics., 40, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, s. 40:1-40:18, Symposium on Computational Geometry, Dallas, Texas, USA, 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. s. 40:1-40:18 40.

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater