Decremental SPQR-trees for planar graphs

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


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

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
Publication statusPublished - 1 Aug 2018
Event26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Duration: 20 Aug 201822 Aug 2018


Conference26th European Symposium on Algorithms, ESA 2018
SeriesLeibniz International Proceedings in Informatics, LIPIcs

    Research areas

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

Number of downloads are based on statistics from Google Scholar and

No data available

ID: 230343791