Contracting a planar graph efficiently

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Standard

Contracting a planar graph efficiently. / Holm, Jacob; Italiano, Giuseppe F.; Karczmarz, Adam; Łacki, Jakub; Rotenberg, Eva; Sankowski, Piotr.

25th European Symposium on Algorithms, ESA 2017. ed. / Christian Sohler; Christian Sohler; Kirk Pruhs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. 50 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 87).

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 & Sankowski, P 2017, Contracting a planar graph efficiently. in C Sohler, C Sohler & K Pruhs (eds), 25th European Symposium on Algorithms, ESA 2017., 50, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 87, 25th European Symposium on Algorithms, ESA 2017, Vienna, Austria, 04/09/2017. https://doi.org/10.4230/LIPIcs.ESA.2017.50

APA

Holm, J., Italiano, G. F., Karczmarz, A., Łacki, J., Rotenberg, E., & Sankowski, P. (2017). Contracting a planar graph efficiently. In C. Sohler, C. Sohler, & K. Pruhs (Eds.), 25th European Symposium on Algorithms, ESA 2017 [50] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 87 https://doi.org/10.4230/LIPIcs.ESA.2017.50

Vancouver

Holm J, Italiano GF, Karczmarz A, Łacki J, Rotenberg E, Sankowski P. Contracting a planar graph efficiently. In Sohler C, Sohler C, Pruhs K, editors, 25th European Symposium on Algorithms, ESA 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2017. 50. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 87). https://doi.org/10.4230/LIPIcs.ESA.2017.50

Author

Holm, Jacob ; Italiano, Giuseppe F. ; Karczmarz, Adam ; Łacki, Jakub ; Rotenberg, Eva ; Sankowski, Piotr. / Contracting a planar graph efficiently. 25th European Symposium on Algorithms, ESA 2017. editor / Christian Sohler ; Christian Sohler ; Kirk Pruhs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 87).

Bibtex

@inproceedings{cf5dc58e89d34e00b3d56123e9293f64,
title = "Contracting a planar graph efficiently",
abstract = "We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access to neighbor lists in O(1) time. Moreover, it can report all the arising self-loops and parallel edges. By applying the data structure, we can achieve optimal running times for decremental bridge detection, 2-edge connectivity, maximal 3-edge connected components, and the problem of finding a unique perfect matching for a static planar graph. Furthermore, we improve the running times of algorithms for several planar graph problems, including decremental 2-vertex and 3- edge connectivity, and we show that using our data structure in a black-box manner, one obtains conceptually simple optimal algorithms for computing MST and 5-coloring in planar graphs.",
keywords = "Algorithms, Coloring, Connectivity, Data structures, Planar graphs",
author = "Jacob Holm and Italiano, {Giuseppe F.} and Adam Karczmarz and Jakub {\L}acki and Eva Rotenberg and Piotr Sankowski",
year = "2017",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.ESA.2017.50",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Christian Sohler and Christian Sohler and Kirk Pruhs",
booktitle = "25th European Symposium on Algorithms, ESA 2017",
note = "25th European Symposium on Algorithms, ESA 2017 ; Conference date: 04-09-2017 Through 06-09-2017",

}

RIS

TY - GEN

T1 - Contracting a planar graph efficiently

AU - Holm, Jacob

AU - Italiano, Giuseppe F.

AU - Karczmarz, Adam

AU - Łacki, Jakub

AU - Rotenberg, Eva

AU - Sankowski, Piotr

PY - 2017/9/1

Y1 - 2017/9/1

N2 - We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access to neighbor lists in O(1) time. Moreover, it can report all the arising self-loops and parallel edges. By applying the data structure, we can achieve optimal running times for decremental bridge detection, 2-edge connectivity, maximal 3-edge connected components, and the problem of finding a unique perfect matching for a static planar graph. Furthermore, we improve the running times of algorithms for several planar graph problems, including decremental 2-vertex and 3- edge connectivity, and we show that using our data structure in a black-box manner, one obtains conceptually simple optimal algorithms for computing MST and 5-coloring in planar graphs.

AB - We present a data structure that can maintain a simple planar graph under edge contractions in linear total time. The data structure supports adjacency queries and provides access to neighbor lists in O(1) time. Moreover, it can report all the arising self-loops and parallel edges. By applying the data structure, we can achieve optimal running times for decremental bridge detection, 2-edge connectivity, maximal 3-edge connected components, and the problem of finding a unique perfect matching for a static planar graph. Furthermore, we improve the running times of algorithms for several planar graph problems, including decremental 2-vertex and 3- edge connectivity, and we show that using our data structure in a black-box manner, one obtains conceptually simple optimal algorithms for computing MST and 5-coloring in planar graphs.

KW - Algorithms

KW - Coloring

KW - Connectivity

KW - Data structures

KW - Planar graphs

UR - http://www.scopus.com/inward/record.url?scp=85030538538&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2017.50

DO - 10.4230/LIPIcs.ESA.2017.50

M3 - Article in proceedings

AN - SCOPUS:85030538538

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 25th European Symposium on Algorithms, ESA 2017

A2 - Sohler, Christian

A2 - Sohler, Christian

A2 - Pruhs, Kirk

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

T2 - 25th European Symposium on Algorithms, ESA 2017

Y2 - 4 September 2017 through 6 September 2017

ER -

ID: 230343909