Decremental SPQR-trees for planar graphs

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedings – Annual report year: 2019Researchpeer-review

Documents

DOI

View graph of relations

We present a decremental data structure for maintaining the SPQR-tree of a planar graph subject to edge contractions and deletions. The update time, amortized over Ω(n) operations, is O(log2 n). Via SPQR-trees, we give a decremental data structure for maintaining 3-vertex connectivity in planar graphs. It answers queries in O(1) time and processes edge deletions and contractions in O(log2 n) amortized time. The previous best supported deletions and insertions in O(√n) time.

Original languageEnglish
Title of host publicationProceedings of 26th European Symposium on Algorithms, ESA 2018
EditorsHannah Bast, Grzegorz Herman, Yossi Azar
Number of pages16
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1 Aug 2018
ISBN (Print)9783959770811
DOIs
Publication statusPublished - 1 Aug 2018
Event26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Duration: 20 Aug 201822 Aug 2018

Conference

Conference26th European Symposium on Algorithms, ESA 2018
CountryFinland
CityHelsinki
Period20/08/201822/08/2018
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume112
ISSN1868-8969
CitationsWeb of Science® Times Cited: No match on DOI

    Research areas

  • Data structures, Graph algorithms, Graph embeddings, Planar graphs, SPQR-trees, Triconnectivity

ID: 193380690