2018/06/28 by Jacob Holm, Giuseppe F. Italiano, Holm, Jacob +7 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1806.10772
openalex publication_date 2018/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. This is an exponential improvement over the previous best bound of O(√(n) ) that has stood for over 20 years. In addition, the previous data structures only supported edge deletions.