Decremental SPQR-trees for planar graphs

Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łacki, Eva Rotenberg

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

12 Downloads (Pure)

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(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. The previous best supported deletions and insertions in O(√n) time.

Original languageEnglish
Title of host publicationProceedings of 26th European Symposium on Algorithms, ESA 2018
EditorsHannah Bast, Grzegorz Herman, Yossi Azar
Number of pages16
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1 Aug 2018
ISBN (Print)9783959770811
DOIs
Publication statusPublished - 1 Aug 2018
Event26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Duration: 20 Aug 201822 Aug 2018

Conference

Conference26th European Symposium on Algorithms, ESA 2018
CountryFinland
CityHelsinki
Period20/08/201822/08/2018
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume112
ISSN1868-8969

Keywords

  • Data structures
  • Graph algorithms
  • Graph embeddings
  • Planar graphs
  • SPQR-trees
  • Triconnectivity

Cite this

Holm, J., Italiano, G. F., Karczmarz, A., Łacki, J., & Rotenberg, E. (2018). Decremental SPQR-trees for planar graphs. In H. Bast, G. Herman, & Y. Azar (Eds.), Proceedings of 26th European Symposium on Algorithms, ESA 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs, Vol.. 112 https://doi.org/10.4230/LIPIcs.ESA.2018.46
Holm, Jacob ; Italiano, Giuseppe F. ; Karczmarz, Adam ; Łacki, Jakub ; Rotenberg, Eva. / Decremental SPQR-trees for planar graphs. Proceedings of 26th European Symposium on Algorithms, ESA 2018. editor / Hannah Bast ; Grzegorz Herman ; Yossi Azar. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 112).
@inproceedings{06bebd3fb9b84c5aa47c7993c1f918e9,
title = "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(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. The previous best supported deletions and insertions in O(√n) time.",
keywords = "Data structures, Graph algorithms, Graph embeddings, Planar graphs, SPQR-trees, Triconnectivity",
author = "Jacob Holm and Italiano, {Giuseppe F.} and Adam Karczmarz and Jakub Łacki and Eva Rotenberg",
year = "2018",
month = "8",
day = "1",
doi = "10.4230/LIPIcs.ESA.2018.46",
language = "English",
isbn = "9783959770811",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Hannah Bast and Grzegorz Herman and Yossi Azar",
booktitle = "Proceedings of 26th European Symposium on Algorithms, ESA 2018",

}

Holm, J, Italiano, GF, Karczmarz, A, Łacki, J & Rotenberg, E 2018, Decremental SPQR-trees for planar graphs. in H Bast, G Herman & Y Azar (eds), Proceedings of 26th European Symposium on Algorithms, ESA 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 112, 26th European Symposium on Algorithms, ESA 2018, Helsinki, Finland, 20/08/2018. https://doi.org/10.4230/LIPIcs.ESA.2018.46

Decremental SPQR-trees for planar graphs. / Holm, Jacob; Italiano, Giuseppe F.; Karczmarz, Adam; Łacki, Jakub; Rotenberg, Eva.

Proceedings of 26th European Symposium on Algorithms, ESA 2018. ed. / Hannah Bast; Grzegorz Herman; Yossi Azar. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 112).

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - Decremental SPQR-trees for planar graphs

AU - Holm, Jacob

AU - Italiano, Giuseppe F.

AU - Karczmarz, Adam

AU - Łacki, Jakub

AU - Rotenberg, Eva

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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. The previous best supported deletions and insertions in O(√n) time.

AB - 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. The previous best supported deletions and insertions in O(√n) time.

KW - Data structures

KW - Graph algorithms

KW - Graph embeddings

KW - Planar graphs

KW - SPQR-trees

KW - Triconnectivity

U2 - 10.4230/LIPIcs.ESA.2018.46

DO - 10.4230/LIPIcs.ESA.2018.46

M3 - Article in proceedings

AN - SCOPUS:85052540763

SN - 9783959770811

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Proceedings of 26th European Symposium on Algorithms, ESA 2018

A2 - Bast, Hannah

A2 - Herman, Grzegorz

A2 - Azar, Yossi

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

ER -

Holm J, Italiano GF, Karczmarz A, Łacki J, Rotenberg E. Decremental SPQR-trees for planar graphs. In Bast H, Herman G, Azar Y, editors, Proceedings of 26th European Symposium on Algorithms, ESA 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 112). https://doi.org/10.4230/LIPIcs.ESA.2018.46