Good r-divisions Imply Optimal Amortised Decremental Biconnectivity
share
We present a data structure that given a graph G of n vertices and m edges, and a suitable pair of 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 O(1) time. In case the vertices are not biconnected, the data structure can return a cut-vertex separating them in O(1) time. As an immediate consequence, this gives optimal amortised decremental biconnectivity, 2-edge connectivity, and connectivity for large classes of graphs, such as planar graphs, minor free graphs, and more.
READ FULL TEXT