@inproceedings{103e97179a11456299ae5a0c6aaca55f,
title = "Good r-divisions imply optimal amortized decremental biconnectivity",
abstract = "We present a data structure that, given a graph G of n vertices and m edges, and a suitable pair of nested r-divisions of G, preprocesses G in O(m + n) time and handles any series of edge-deletions in O(m) total time while answering queries to pairwise biconnectivity in worst-case O(1) time. In case the vertices are not biconnected, the data structure can return a cutvertex separating them in worst-case O(1) time. As an immediate consequence, this gives optimal amortized decremental biconnectivity, 2-edge connectivity, and connectivity for large classes of graphs, including planar graphs and other minor free graphs. ",
keywords = "2-connectivity, Dynamic graphs, Graph minors, Graph separators, R-divisions",
author = "Jacob Holm and Eva Rotenberg",
year = "2021",
doi = "10.4230/LIPIcs.STACS.2021.42",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "1--18",
editor = "Markus Blaser and Benjamin Monmege",
booktitle = "38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021",
note = "38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 ; Conference date: 16-03-2021 Through 19-03-2021",
}