Contracting a planar graph efficiently
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- OA-Contracting a Planar Graph Efficiently∗
Final published version, 605 KB, PDF document
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.
Original language | English |
---|---|
Title of host publication | 25th European Symposium on Algorithms, ESA 2017 |
Editors | Christian Sohler, Christian Sohler, Kirk Pruhs |
Number of pages | 15 |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 1 Sep 2017 |
Article number | 50 |
ISBN (Electronic) | 9783959770491 |
DOIs | |
Publication status | Published - 1 Sep 2017 |
Event | 25th European Symposium on Algorithms, ESA 2017 - Vienna, Austria Duration: 4 Sep 2017 → 6 Sep 2017 |
Conference
Conference | 25th European Symposium on Algorithms, ESA 2017 |
---|---|
Land | Austria |
By | Vienna |
Periode | 04/09/2017 → 06/09/2017 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 87 |
ISSN | 1868-8969 |
- Algorithms, Coloring, Connectivity, Data structures, Planar graphs
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
ID: 230343909