Document Open Access Logo

Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast

Authors Markus Chimani , Tilo Wiedera

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2018.19.pdf
  • Filesize: 493 kB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Mathematics of computing → Graph theory
  • Theory of computation → Linear programming
Keywords
  • algorithm engineering
  • graph algorithms
  • integer linear programming
  • maximum planar subgraph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The NP-hard Maximum Planar Subgraph problem asks for a planar subgraph H of a given graph G such that H has maximum edge cardinality. For more than two decades, the only known non-trivial exact algorithm was based on integer linear programming and Kuratowski's famous planarity criterion. We build upon this approach and present new constraint classes - together with a lifting of the polyhedron - to obtain provably stronger LP-relaxations, and in turn faster algorithms in practice. The new constraints take Euler's polyhedron formula as a starting point and combine it with considering cycles in G. This paper discusses both the theoretical as well as the practical sides of this strengthening.

Cite As Get BibTex

Markus Chimani and Tilo Wiedera. Cycles to the Rescue! Novel Constraints to Compute Maximum Planar Subgraphs Fast. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.19

Author Details

Markus Chimani
  • Theoretical Computer Science, Osnabrück University, Germany
Tilo Wiedera
  • Theoretical Computer Science, Osnabrück University, Germany

Funding

Supported by the German Research Foundation (DFG) project CH 897/2-1.

References

  1. Carlo Batini, Maurizio Talamo, and Roberto Tamassia. Computer Aided Layout of Entity Relationship Diagrams. J. Syst. Soft., 4(2-3):163-173, 1984. URL: http://dx.doi.org/10.1016/0164-1212(84)90006-2.
  2. Gruia Călinescu, Cristina Gomes Fernandes, Ulrich Finkler, and Howard Karloff. A Better Approximation Algorithm for Finding Planar Subgraphs. J. Alg. in Cognition, Informatics and Logic, 27(2):269-302, 1998. URL: http://dx.doi.org/10.1006/jagm.1997.0920.
  3. Parinya Chalermsook and Andreas Schmid. Finding Triangles for Maximum Planar Subgraphs. In Sheung-Hung Poon, Md. Saidur Rahman, and Hsu-Chun Yen, editors, WALCOM: Algorithms and Computation, 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29-31, 2017, Proceedings., volume 10167 of Lecture Notes in Computer Science, pages 373-384. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-53925-6_29.
  4. Markus Chimani and Carsten Gutwenger. Non-planar core reduction of graphs. Discrete Mathematics, 309(7):1838-1855, 2009. URL: http://dx.doi.org/10.1016/j.disc.2007.12.078.
  5. Markus Chimani and Carsten Gutwenger. Advances in the Planarization Method: Effective Multiple Edge Insertions. J. Graph Algorithms Appl., 13(3):729-757, 2012. URL: http://dx.doi.org/10.7155/jgaa.00264.
  6. Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel. The Open Graph Drawing Framework (OGDF). In Roberto Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 543-569. Chapman and Hall/CRC, 2013. URL: https://crcpress.com/Handbook-of-Graph-Drawing-and-Visualization/Tamassia/9781584884125.
  7. Markus Chimani, Ivo Hedtke, and Tilo Wiedera. Limits of Greedy Approximation Algorithms for the Maximum Planar Subgraph Problem. In Veli Mäkinen, Simon J. Puglisi, and Leena Salmela, editors, Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings, volume 9843 of Lecture Notes in Computer Science, pages 334-346. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-44543-4_26.
  8. Markus Chimani, Ivo Hedtke, and Tilo Wiedera. Exact Algorithms for the Maximum Planar Subgraph Problem: New Models and Experiments. In 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L'Aquila, Italy, volume 103. LIPIcs, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.SEA.2018.22.
  9. Markus Chimani and Petr Hlinený. A tighter insertion-based approximation of the crossing number. J. Comb. Optim., 33(4):1183-1225, 2017. URL: http://dx.doi.org/10.1007/s10878-016-0030-z.
  10. Markus Chimani, Karsten Klein, and Tilo Wiedera. A Note on the Practicality of Maximal Planar Subgraph Algorithms. In Yifan Hu and Martin Nöllenburg, editors, Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016), volume abs/1609.02443. CoRR, 2016. URL: http://dx.doi.org/10.1007/978-3-319-50106-2_28.
  11. Markus Chimani, Petra Mutzel, and Jens M. Schmidt. Efficient Extraction of Multiple Kuratowski Subdivisions. In Seok-Hee Hong, Takao Nishizeki, and Wu Quan, editors, Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007. Revised Papers, volume 4875 of Lecture Notes in Computer Science, pages 159-170. Springer, 2007. URL: http://dx.doi.org/10.1007/978-3-540-77537-9_17.
  12. Giuseppe Di Battista, Ashim Garg, Giuseppe Liotta, Roberto Tamassia, Emanuele Tassinari, and Francesco Vargiu. An experimental comparison of four graph drawing algorithms. Computational Geometry. Theory and Applications, 7(5-6):303-325, 1997. 11th ACM Symposium on Computational Geometry (Vancouver, BC, 1995). URL: http://dx.doi.org/10.1016/S0925-7721(96)00005-3.
  13. Manuel Fernández, Nicholas Sieger, and Michael Tait. Maximal Planar Subgraphs of Fixed Girth in Ramdom Graphs. CoRR, 2018. URL: http://arxiv.org/abs/1706.06202.
  14. Michael R. Garey and David S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman and Co., San Francisco, Calif., 1979. Google Scholar
  15. Ivo Hedtke. Minimum Genus and Maximum Planar Subgraph: Exact Algorithms and General Limits of Approximation Algorithms. PhD thesis, Osnabrück University, 2017. URL: https://repositorium.ub.uos.de/handle/urn:nbn:de:gbv:700-2017082416212.
  16. Jan M. Hochstein and Karsten Weihe. Maximum s-t-flow with k crossings in O(k³ n log n) time. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, SODA '07, pages 843-847, 2007. Google Scholar
  17. Michael Jünger and Petra Mutzel. Maximum Planar Subgraphs and Nice Embeddings: Practical Layout Tools. Algorithmica, 16(1):33-59, 1996. URL: http://dx.doi.org/10.1007/s004539900036.
  18. Thorsten Koch, Alexander Martin, and Stefan Voß. SteinLib: An updated library on steiner tree problems in graphs. Technical Report ZIB-Report 00-37, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, Berlin, 2000. URL: http://elib.zib.de/steinlib.
  19. Kazimierz Kuratowski. Sur le problème des courbes gauches en topologie. Fundamenta Mathematicae, 15:271-283, 1930. Google Scholar
  20. P. C. Liu and R. C. Geldmacher. On the deletion of nonplanar edges of a graph. In Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), Congress. Numer., XXIII-XXIV, pages 727-738. Utilitas Math., Winnipeg, Man., 1979. Google Scholar
  21. Stephen J. Maher, Tobias Fischer, Tristan Gally, Gerald Gamrath, Ambros Gleixner, Robert Lion Gottwald, Gregor Hendel, Thorsten Koch, Marco E. Lübbecke, Matthias Miltenberger, Benjamin Müller, Marc E. Pfetsch, Christian Puchert, Daniel Rehfeldt, Sebastian Schenker, Robert Schwarz, Felipe Serrano, Yuji Shinano, Dieter Weninger, Jonas T. Witt, and Jakob Witzig. The SCIP Optimization Suite 4.0. Technical Report 17-12, ZIB, Takustr. 7, 14195 Berlin, 2017. Google Scholar
  22. Michael Mitzenmacher and Eli Upfal. Probability and computing - randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. Google Scholar
  23. Petra Mutzel. The maximum planar subgraph problem. PhD thesis, Köln University, 1994. Google Scholar
  24. Stephen C. North. 5114 directed graphs, 1995. Manuscript. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »