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 metadatas

Cited literature [56 references]  Display  Hide  Download

https://hal.inria.fr/hal-01925961
Contributor : Marie-France Sagot <>
Submitted on : Sunday, November 18, 2018 - 4:34:51 PM
Last modification on : Wednesday, June 12, 2019 - 3:30:02 PM
Long-term archiving on : Tuesday, February 19, 2019 - 1:07:27 PM

File

1806.10772.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

26

Files downloads

233