Decremental SPQR-trees for planar graphs

Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łacki, Eva Rotenberg

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

6 Citations (Scopus)
97 Downloads (Pure)

Abstract

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 publication26th 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
Article number46
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
Country/TerritoryFinland
CityHelsinki
Period20/08/201822/08/2018
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume112
ISSN1868-8969

Keywords

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

Cite this