Article,
Good r-divisions Imply Optimal Amortized Decremental Biconnectivity
Affiliations
- [1] University of Copenhagen [NORA names: KU University of Copenhagen; University; Denmark; Europe, EU; Nordic; OECD];
- [2] Technical University of Denmark [NORA names: DTU Technical University of Denmark; University; Denmark; Europe, EU; Nordic; OECD]
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)$$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
O(1,
O(1) time,
O(m,
biconnectivity,
class,
classes of graphs,
connection,
consequences,
cutvertex,
data,
data structure,
data structures,
edge,
edge-deletion,
graph,
graph G,
planar graphs,
query,
structure,
time,
total time,
vertices