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.
|Conference||38th International Symposium on Theoretical Aspects of Computer Science|
|Period||16/03/2021 → 19/03/2021|
|Series||Leibniz International Proceedings in Informatics|
- Dynamic graphs
- Graph minors
- Graph separators