@inproceedings{a17cbc6fd3c34899b241b3ea694d128e,
title = "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(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.",
keywords = "Data structures, Graph algorithms, Graph embeddings, Planar graphs, SPQR-trees, Triconnectivity",
author = "Jacob Holm and Italiano, {Giuseppe F.} and Adam Karczmarz and Jakub {\L}acki and Eva Rotenberg",
year = "2018",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.ESA.2018.46",
language = "English",
isbn = "9783959770811",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Hannah Bast and Grzegorz Herman and Yossi Azar",
booktitle = "26th European Symposium on Algorithms, ESA 2018",
note = "26th European Symposium on Algorithms, ESA 2018 ; Conference date: 20-08-2018 Through 22-08-2018",
}