Google Research

Decremental SPQR-trees for Planar Graphs

  • Adam Karczmarz
  • Eva Rotenberg
  • Giuseppe F. Italiano
  • Jacob Holm
  • Jakub Łącki
ESA 2018

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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work