Can I read Decremental SPQR-trees for Planar Graphs on EtoBox?

Decremental SPQR-trees for Planar Graphs by Holm, Jacob; Italiano, Giuseppe F.; Karczmarz, Adam; Łącki, Jakub; Rotenberg, Eva is a scholarly article available to read on EtoBox.

What is Decremental SPQR-trees for Planar Graphs about?

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 $\Omega(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(\sqrt{n}\,)$ that has stood for over 20 years. In addition, the previous data structures only supported edge deletions.

Author

Holm, Jacob; Italiano, Giuseppe F.; Karczmarz, Adam; Łącki, Jakub; Rotenberg, Eva

Published

2018

Language

EN