×

zbMATH — the first resource for mathematics

Exact algorithms for the maximum planar subgraph problem: new models and experiments. (English) Zbl 07286695
D’Angelo, Gianlorenzo (ed.), 17th symposium on experimental algorithms, SEA 2018, June 27–29, 2018, L’Aquila, Italy. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-070-5). LIPIcs – Leibniz International Proceedings in Informatics 103, Article 22, 15 p. (2018).
Summary: Given a graph \(G\), the NP-hard Maximum Planar Subgraph problem asks for a planar subgraph of \(G\) with the maximum number of edges. The only known non-trivial exact algorithm utilizes Kuratowski’s famous planarity criterion and can be formulated as an integer linear program (ILP) or a pseudo-boolean satisfiability problem (PBS). We examine three alternative characterizations of planarity regarding their applicability to model maximum planar subgraphs. For each, we consider both ILP and PBS variants, investigate diverse formulation aspects, and evaluate their practical performance.
For the entire collection see [Zbl 1390.68017].
MSC:
68Wxx Algorithms in computer science
Software:
OGDF; Potassco; SCIP; SteinLib
PDF BibTeX XML Cite
Full Text: DOI
References:
[2] Carlo Batini, Maurizio Talamo, and Roberto Tamassia. Computer aided layout of entity relationship diagrams. \it Journal of Systems and Software, 4(2-3):163-173, 1984. doi:10. 1016/0164-1212(84)90006-2.
[3] Stephan Beyer, Markus Chimani, Ivo Hedtke, and Michal Kotrbčík. A Practical Method for the Minimum Genus of a Graph: Models and Experiments.In Andrew V. Goldberg and Alexander S. Kulikov, editors, \it Experimental Algorithms - 15th International \it Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings, volume 9685 of \it Lecture Notes in Computer Science, pages 75-88. Springer, 2016. doi:10.1007/ 978-3-319-38851-9_6.
[4] John M. Boyer and Wendy J. Myrvold. On the Cutting Edge: Simplified \it O(\it n) Planarity by Edge Addition.\it Journal of Graph Algorithms and Applications, 8(3):241-273, 2004. doi:10.7155/jgaa.00091.
[5] Gruia Călinescu, Cristina Gomes Fernandes, Ulrich Finkler, and Howard Karloff. A Better Approximation Algorithm for Finding Planar Subgraphs. \it Journal of Algorithms. Cogni- \it tion, Informatics and Logic, 27(2):269-302, 1998. 7th Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996). doi:10.1006/jagm.1997.0920.
[6] Alberto Caprara, Marcus Oswald, Gerhard Reinelt, Robert Schwarz, and Emiliano Traversi. Optimal linear arrangements using betweenness variables.\it Mathematical Programming \it Computation, 3(3):261-280, 2011. doi:10.1007/s12532-011-0027-7.
[7] Parinya Chalermsook and Andreas Schmid.Finding triangles for maximum planar subgraphs.In Sheung-Hung Poon, Md. Saidur Rahman, and Hsu-Chun Yen, editors, \it WALCOM: Algorithms and Computation, 11th International Conference and Workshops, \it WALCOM 2017, Hsinchu, Taiwan, March 29-31, 2017, Proceedings., volume 10167 of \it Lecture Notes in Computer Science, pages 373-384. Springer, 2017.doi:10.1007/ 978-3-319-53925-6_29.
[8] Markus Chimani and Carsten Gutwenger. Non-planar core reduction of graphs. \it Discrete \it Mathematics, 309(7):1838-1855, 2009. doi:10.1016/j.disc.2007.12.078.
[9] Markus Chimani and Carsten Gutwenger. Advances in the planarization method: effective mutiple edge insertions. \it Journal of Graph Algorithms and Applications, 16(3):729-757, 2012. doi:10.7155/jgaa.00264.
[10] 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, \it Handbook on Graph Drawing and Visualization, pages 543-569. Chapman and Hall/CRC, 2013. URL: crcpress.com/Handbook-of-Graph-Drawing-and-Visualization/ Tamassia/9781584884125.
[11] Markus Chimani and Petr Hlinený. A tighter insertion-based approximation of the crossing number. \it Journal of Combinatorial Optimization, 33(4):1183-1225, 2017. doi:10.1007/ s10878-016-0030-z.
[12] 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, \it Proceedings \it of the 24th International Symposium on Graph Drawing and Network Visualization (GD \it 2016), volume abs/1609.02443. CoRR, 2016.
[13] Markus Chimani, Petra Mutzel, and Jens M. Schmidt. Efficient extraction of multiple kuratowski subdivisions. In Seok-Hee Hong, Takao Nishizeki, and Wu Quan, editors, \it Graph \it Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, \it 2007. Revised Papers, volume 4875 of \it Lecture Notes in Computer Science, pages 159-170. Springer, 2007. doi:10.1007/978-3-540-77537-9_17.
[14] H. de Fraysseix and P. Rosenstiehl.A characterization of planar graphs by Trémaux orders. \it Combinatorica. An International Journal of the János Bolyai Mathematical Society, 5(2):127-135, 1985. doi:10.1007/BF02579375.
[15] Giuseppe Di Battista, Ashim Garg, Giuseppe Liotta, Roberto Tamassia, Emanuele Tassinari, and Francesco Vargiu.An experimental comparison of four graph drawing algorithms. \it Computational Geometry. Theory and Applications, 7(5-6):303-325, 1997. 11th ACM Symposium on Computational Geometry (Vancouver, BC, 1995). doi:10.1016/ S0925-7721(96)00005-3.
[16] Ben Dushnik and E. W. Miller. Partially ordered sets. \it American Journal of Mathematics, 63:600-610, 1941. doi:10.2307/2371374.
[17] Michael R. Garey and David S. Johnson. \it Computers and intractability. A guide to the \it theory of NP-completeness. W. H. Freeman and Co., San Francisco, Calif., 1979.
[18] Martin Gebser, Benjamin Kaufmann, Roland Kaminski, Max Ostrowski, Torsten Schaub, and Marius Thomas Schneider. Potassco: The potsdam answer set solving collection. \it AI \it Communications, 24(2):107-124, 2011. doi:10.3233/AIC-2011-0491.
[19] Ivo Hedtke. \it Minimum Genus and Maximum Planar Subgraph: Exact Algorithms and Gen- \it eral Limits of Approximation Algorithms. PhD thesis, Osnabrück University, 2017. URL: repositorium.ub.uos.de/handle/urn:nbn:de:gbv:700-2017082416212.
[20] Jan M. Hochstein and Karsten Weihe. Maximum \it s-\it t-flow with \it k crossings in \it O(\it kn log \it n) time. In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, \it Proceedings of the Eigh- \it teenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Or- \it leans, Louisiana, USA, January 7-9, 2007, pages 843-847. SIAM, 2007.URL: http: //dl.acm.org/citation.cfm?id=1283383.1283473.
[21] Michael Jünger and Petra Mutzel. Maximum Planar Subgraphs and Nice Embeddings: Practical Layout Tools.\it Algorithmica. An International Journal in Computer Science, 16(1):33-59, 1996. doi:10.1007/s004539900036.
[22] T. Koch, A. Martin, and S. 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.
[23] Kazimierz Kuratowski. Sur le problème des courbes gauches en topologie. \it Fundamenta \it Mathematicae, 15:271-283, 1930.
[24] :15
[25] :14
[26] Charles H. C. Little and G. Sanjith. Another characterisation of planar graphs. \it Electronic \it Journal of Combinatorics, 17(1):Note 15, 7, 2010.
[27] P. C. Liu and R. C. Geldmacher. On the deletion of nonplanar edges of a graph. In \it Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and \it Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), Congress. Numer., XXIII- XXIV, pages 727-738. Utilitas Math., Winnipeg, Man., 1979.
[28] 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.
[29] Petra Mutzel. \it The maximum planar subgraph problem. PhD thesis, Köln University, 1994.
[30] Stephen C. North. 5114 directed graphs, 1995. Manuscript.
[31] Walter Schnyder. Planar Graphs and Poset Dimension. \it Order. A Journal on the Theory \it of Ordered Sets and its Applications, 5(4):323-343, 1989. doi:10.1007/BF00353652.
[32] A. Steger and N. C. Wormald. Generating random regular graphs quickly. \it Combinatorics, \it Probability and Computing, 8(4):377-396, 1999. Random graphs and combinatorial structures (Oberwolfach, 1997). doi:10.1017/S0963548399003867.
[33] Edward Szpilrajn. Sur l’extension de l’ordre partiel. \it Fundamenta Mathematicae, 16(1):386- 389, 1930. URL: http://eudml.org/doc/212499.
[34] Carsten Thomassen. Planarity and Duality of Finite and Infinite Graphs. \it Journal of Com- \it binatorial Theory. Series B, 29(2):244-271, 1980. doi:10.1016/0095-8956(80)90083-0.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.