Standard
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
Harvard
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
APA
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
Vancouver
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
Author
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).
Bibtex
@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",
}
RIS
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 -
