Decremental SPQR-trees for Planar Graphs

Adam Karczmarz
Eva Rotenberg
Giuseppe F. Italiano
Jacob Holm
ESA 2018
Google Scholar


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.