Standard
Decremental SPQR-trees for planar graphs. / Holm, Jacob; Italiano, Giuseppe F.; Karczmarz, Adam; Łacki, Jakub; Rotenberg, Eva.
26th European Symposium on Algorithms, ESA 2018. ed. / Hannah Bast; Grzegorz Herman; Yossi Azar. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. 46 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 112).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
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),
26th European Symposium on Algorithms, ESA 2018., 46, 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
APA
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.),
26th European Symposium on Algorithms, ESA 2018 [46] 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
Vancouver
Holm J, Italiano GF, Karczmarz A, Łacki J, Rotenberg E.
Decremental SPQR-trees for planar graphs. In Bast H, Herman G, Azar Y, editors, 26th European Symposium on Algorithms, ESA 2018. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2018. 46. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 112).
https://doi.org/10.4230/LIPIcs.ESA.2018.46
Author
Holm, Jacob ; Italiano, Giuseppe F. ; Karczmarz, Adam ; Łacki, Jakub ; Rotenberg, Eva. / Decremental SPQR-trees for planar graphs. 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).
Bibtex
@inproceedings{a17cbc6fd3c34899b241b3ea694d128e,
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 {\L}acki and Eva Rotenberg",
year = "2018",
month = aug,
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 = "26th European Symposium on Algorithms, ESA 2018",
note = "26th European Symposium on Algorithms, ESA 2018 ; Conference date: 20-08-2018 Through 22-08-2018",
}
RIS
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
UR - http://www.scopus.com/inward/record.url?scp=85052540763&partnerID=8YFLogxK
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 - 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
T2 - 26th European Symposium on Algorithms, ESA 2018
Y2 - 20 August 2018 through 22 August 2018
ER -
