Good r-divisions Imply Optimal Amortized Decremental Biconnectivity

Jacob Holm, Eva Rotenberg

Research output: Contribution to journalJournal articleResearchpeer-review

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.

Original languageEnglish
JournalTheory of Computing Systems
Volume68
Pages (from-to)1014–1048
ISSN1432-4350
DOIs
Publication statusPublished - 2024

Keywords

  • 2-connectivity
  • Dynamic graphs
  • Graph minors

Fingerprint

Dive into the research topics of 'Good r-divisions Imply Optimal Amortized Decremental Biconnectivity'. Together they form a unique fingerprint.

Cite this