Skip to Main content Skip to Navigation
New interface
Conference papers

Decremental SPQR-trees for Planar Graphs

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(log 2 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(log 2 n) amortized time. This is an exponential improvement over the previous best bound of O(√ n) that has stood for over 20 years. In addition, the previous data structures only supported edge deletions.
Document type :
Conference papers
Complete list of metadata

Cited literature [59 references]  Display  Hide  Download
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Sunday, November 18, 2018 - 4:34:51 PM
Last modification on : Friday, November 18, 2022 - 9:23:22 AM
Long-term archiving on: : Tuesday, February 19, 2019 - 1:07:27 PM


Files produced by the author(s)


  • HAL Id : hal-01925961, version 1
  • ARXIV : 1806.10772



Jacob Holm, Giuseppe F Italiano, Adam Karczmarz, Jakub Łącki, Eva Rotenberg. Decremental SPQR-trees for Planar Graphs. European Symposium on Algorithms, 2018, Helsinki, Finland. ⟨hal-01925961⟩



Record views


Files downloads