Decremental SPQR-trees for Planar Graphs
Abstract
We present a decremental data structure for maintaining the SPQR-tree of a planar graph, subject to contractions and deletions of edges. The amortized update time is O(log^2 n). Via SPQR-trees, we show a data structure that maintains 3-vertex connectivity in planar graphs, answers queries in O(1) time and processes edge deletions and contractions in O(log^2 n) time (amortized over Omega(n) updates).
This is an exponential improvement over a previously known O(sqrt(n)) bound that has stood for over 20 years.
Research Areas
