Good r-Divisions Imply Optimal Amortized Decremental Biconnectivity

Jacob Holm, Eva Rotenberg

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-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
Title of host publicationProceedings of 38th International Symposium on Theoretical Aspects of Computer Science
Number of pages18
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date2021
Article number42
ISBN (Print)9783959771801
DOIs
Publication statusPublished - 2021
Event38th International Symposium on Theoretical Aspects of Computer Science - Online event, Saarbücken , Germany
Duration: 16 Mar 202119 Mar 2021

Conference

Conference38th International Symposium on Theoretical Aspects of Computer Science
LocationOnline event
CountryGermany
CitySaarbücken
Period16/03/202119/03/2021
SeriesLeibniz International Proceedings in Informatics
Volume187
ISSN1868-8969

Keywords

  • Dynamic graphs
  • 2-connectivity
  • Graph minors
  • r-divisions
  • Graph separators

Fingerprint Dive into the research topics of 'Good <i>r</i>-Divisions Imply Optimal Amortized Decremental Biconnectivity'. Together they form a unique fingerprint.

Cite this