Conference paper
Decremental SPQR-trees for planar graphs
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.
Language: | English |
---|---|
Publisher: | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Year: | 2018 |
Proceedings: | 26th European Symposium on Algorithms, ESA 2018European Symposium on Algorithms |
Series: | Leibniz International Proceedings in Informatics, Lipics |
ISBN: | 3959770812 and 9783959770811 |
ISSN: | 18688969 |
Types: | Conference paper |
DOI: | 10.4230/LIPIcs.ESA.2018.46 |
ORCIDs: | 0000-0001-6997-9251 and Rotenberg, Eva |