Decremental SPQR-trees for Planar Graphs

Abstract : 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(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(√ n) that has stood for over 20 years. In addition, the previous data structures only supported edge deletions.
Type de document :
Communication dans un congrès
European Symposium on Algorithms, 2018, Helsinki, Finland
Liste complète des métadonnées

https://hal.inria.fr/hal-01925961
Contributeur : Marie-France Sagot <>
Soumis le : dimanche 18 novembre 2018 - 16:34:51
Dernière modification le : lundi 18 février 2019 - 10:18:02
Document(s) archivé(s) le : mardi 19 février 2019 - 13:07:27

Fichier

1806.10772.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01925961, version 1
  • ARXIV : 1806.10772

Collections

Citation

Jacob Holm, Giuseppe Italiano, Adam Karczmarz, Jakub Łącki, Eva Rotenberg. Decremental SPQR-trees for Planar Graphs. European Symposium on Algorithms, 2018, Helsinki, Finland. 〈hal-01925961〉

Partager

Métriques

Consultations de la notice

8

Téléchargements de fichiers

23