LIPIcs.ESA.2017.50.pdf
- Filesize: 0.59 MB
- 15 pages
Document
Contracting a Planar Graph Efficiently
Authors
-
Part of:
Volume:
25th Annual European Symposium on Algorithms (ESA 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-09-01
Cite AsGet BibTex
Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg, and Piotr Sankowski. Contracting a Planar Graph Efficiently. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ESA.2017.50
https://doi.org/10.4230/LIPIcs.ESA.2017.50
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
- planar graphs
- algorithms
- data structures
- connectivity
- coloring
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Gerth Stølting Brodal and Rolf Fagerberg. Dynamic representation of sparse graphs. In Algorithms and Data Structures, 6th International Workshop, WADS '99, Vancouver, British Columbia, Canada, August 11-14, 1999, Proceedings, pages 342-351, 1999. URL: http://dx.doi.org/10.1007/3-540-48447-7_34.
- Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, and Nikos Parotsidis. Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1900-1918, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.124.
- Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert Endre Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23(4):738-761, 1994. URL: http://dx.doi.org/10.1137/S0097539791194094.
-
Jack Edmonds. Paths, trees and flowers. Canadian Journal of Mathematics, pages 449-467, 1965.
- Greg N. Frederickson. On linear-time algorithms for five-coloring planar graphs. Inf. Process. Lett., 19(5):219-224, 1984. URL: http://dx.doi.org/10.1016/0020-0190(84)90056-5.
- Harold N. Gabow, Haim Kaplan, and Robert Endre Tarjan. Unique maximum matching algorithms. J. Algorithms, 40(2):159-183, 2001. Announced at STOC'99. URL: http://dx.doi.org/10.1006/jagm.2001.1167.
- Dora Giammarresi and Giuseppe F. Italiano. Decremental 2- and 3-connectivity on planar graphs. Algorithmica, 16(3):263-287, 1996. URL: http://dx.doi.org/10.1007/BF01955676.
- Michael T. Goodrich. Planar separators and parallel polygon triangulation. J. Comput. Syst. Sci., 51(3):374-389, 1995. URL: http://dx.doi.org/10.1006/jcss.1995.1076.
- Jens Gustedt. Efficient union-find for planar graphs and other sparse graph classes. Theor. Comput. Sci., 203(1):123-141, 1998. URL: http://dx.doi.org/10.1016/S0304-3975(97)00291-0.
- Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, Eva Rotenberg, and Piotr Sankowski. Contracting a planar graph efficiently, 2017. URL: http://arxiv.org/abs/1706.10228.
-
David R. Karger. Global min-cuts in rnc, and other ramifications of a simple min-out algorithm. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'93, pages 21-30, Philadelphia, PA, USA, 1993. Society for Industrial and Applied Mathematics.
- Philip N. Klein and Shay Mozes. Optimization algorithms for planar graphs, 2017. URL: http://planarity.org.
- Philip N. Klein, Shay Mozes, and Christian Sommer. Structured recursive separator decompositions for planar graphs in linear time. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 505-514, 2013. URL: http://dx.doi.org/10.1145/2488608.2488672.
- \sortkeyLzzzeJakub Łącki and Piotr Sankowski. Optimal decremental connectivity in planar graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 608-621, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.608.
-
Martin Mareš. Two linear time algorithms for mst on minor closed graph classes. Archivum mathematicum, 40(3):315-320, 2002.
- Tomomi Matsui. The minimum spanning tree problem on a planar graph. Discrete Applied Mathematics, 58(1):91-94, 1995. URL: http://dx.doi.org/10.1016/0166-218X(94)00095-U.
-
David W. Matula, Yossi Shiloach, and Robert E. Tarjan. Two linear-time algorithms for five-coloring a planar graph. Technical report, Stanford University, Stanford, CA, USA, 1980.
- Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas. Efficiently four-coloring planar graphs. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC'96, pages 571-575, New York, NY, USA, 1996. ACM. URL: http://dx.doi.org/10.1145/237814.238005.
- Freek van Walderveen, Norbert Zeh, and Lars Arge. Multiway simple cycle separators and I/O-efficient algorithms for planar graphs. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 901-918, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.65.