2026-08-17T17:47:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13687 2024-03-06T10:52:40Z ddc:004 open_access

Good r-Divisions Imply Optimal Amortized Decremental Biconnectivity Holm, Jacob Rotenberg, Eva Dynamic graphs 2-connectivity graph minors r-divisions graph separators 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jacob Holm and Eva Rotenberg 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.42 urn:nbn:de:0030-drops-136875 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.42 eng https://creativecommons.org/licenses/by/4.0/legalcode