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
APA
Vancouver
Author
Bibtex
}
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