Document Open Access Logo

SAT-Based Generation of Planar Graphs

Authors Markus Kirchweger , Manfred Scheucher , Stefan Szeider

PDF
Thumbnail PDF

File

LIPIcs.SAT.2023.14.pdf
  • Filesize: 0.69 MB
  • 18 pages

Document Identifiers

Author Details

Markus Kirchweger
  • Algorithms and Complexity Group, TU Wien, Austria
Manfred Scheucher
  • Institut für Mathematik, Technische Universität Berlin, Germany
Stefan Szeider
  • Algorithms and Complexity Group, TU Wien, Austria

Funding

M.K. and S.S. were supported by the Austrian Science Fund (FWF), project P32441, and from the Vienna Science and Technology Fund (WWTF), project ICT19-065. M.S. was supported by DFG Grant SCHE 2214/1-1.

Cite As Get BibTex

Markus Kirchweger, Manfred Scheucher, and Stefan Szeider. SAT-Based Generation of Planar Graphs. In 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 271, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SAT.2023.14

Abstract

To test a graph’s planarity in SAT-based graph generation we develop SAT encodings with dynamic symmetry breaking as facilitated in the SAT modulo Symmetry (SMS) framework. We implement and compare encodings based on three planarity criteria. In particular, we consider two eager encodings utilizing order-based and universal-set-based planarity criteria, and a lazy encoding based on Kuratowski’s theorem. The performance and scalability of these encodings are compared on two prominent problems from combinatorics: the computation of planar Turán numbers and the Earth-Moon problem. We further showcase the power of SMS equipped with a planarity encoding by verifying and extending several integer sequences from the Online Encyclopedia of Integer Sequences (OEIS) related to planar graph enumeration. Furthermore, we extend the SMS framework to directed graphs which might be of independent interest.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Solvers
  • Mathematics of computing → Graph enumeration
  • Theory of computation → Automated reasoning
  • Hardware → Theorem proving and SAT solving
Keywords
  • SAT modulo Symmetry (SMS)
  • dynamic symmetry breaking
  • planarity test
  • universal point set
  • order dimension
  • Schnyder’s theorem
  • Kuratowski’s theorem
  • Turán’s theorem
  • Earth-Moon problem

Metrics

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

Supplementary Materials

References

  1. David Abrahams et al. Boost C++ Libraries. URL: http://www.boost.org/.
  2. Martin Aigner and Günter M. Ziegler. Proofs from The Book, chapter Chapter 41: Turán’s graph theorem, pages 285-289. Springer, Berlin, sixth edition, 2018. URL: https://doi.org/10.1007/978-3-662-57265-8.
  3. Kenneth Appel and Wolfgang Haken. The solution of the four-color-map problem. Sci. Amer., 237(4):108-121, 152, 1977. URL: https://doi.org/10.1038/scientificamerican1077-108.
  4. Michael J. Bannister, Zhanpeng Cheng, William E. Devanny, and David Eppstein. Superpatterns and universal point sets. J. Graph Algorithms Appl., 18(2):177-209, 2014. URL: https://doi.org/10.7155/jgaa.00318.
  5. Béla Bollobás. Extremal graph theory. Academic Press, 1978. Google Scholar
  6. John A. Bondy and Uppaluri S.R. Murty. Graph Theory. Springer Verlag, 1st edition, 2008. Google Scholar
  7. John M. Boyer and Wendy J. Myrvold. On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. J. Graph Algorithms Appl., 8(3):241-273, 2004. URL: https://doi.org/10.7155/jgaa.00091.
  8. Gunnar Brinkmann and Brendan D. McKay. Fast generation of planar graphs. MATCH Communications in Mathematical and in Computer Chemistry, 58(2):323-357, 2007. Google Scholar
  9. Jean Cardinal, Michael Hoffmann, and Vincent Kusters. On universal point sets for planar graphs. In Computational Geometry and Graphs, pages 30-41. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-45281-9_3.
  10. Markus Chimani, Ivo Hedtke, and Tilo Wiedera. Exact algorithms for the maximum planar subgraph problem: New models and experiments. ACM J. Exp. Algorithmics, 24(1):2.1:1-2.1:21, 2019. URL: https://doi.org/10.1145/3320344.
  11. Stephen A. Cook and Robert A. Reckhow. Time bounded random access machines. Journal of Computer and System Sciences, 7(4):354-375, 1973. URL: https://doi.org/10.1016/S0022-0000(73)80029-7.
  12. Daniel W. Cranston, Bernard Lidický, Xiaonan Liu, and Abhinav shantanam. Planar Turán numbers of cycles: a counterexample. Electron. J. Combin., 29(3):Paper No. 3.31, 10, 2022. URL: https://doi.org/10.37236/10774.
  13. Hubert de Fraysseix, János Pach, and Richard Pollack. Small Sets Supporting Fary Embeddings of Planar Graphs. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC'88), pages 426-433. Association for Computing Machinery, 1988. URL: https://doi.org/10.1145/62212.62254.
  14. Chris Dowden. Extremal C₄-free/C₅-free planar graphs. J. Graph Theory, 83(3):213-230, 2016. URL: https://doi.org/10.1002/jgt.21991.
  15. Liangli Du, Bing Wang, and Mingqing Zhai. Planar Turán numbers on short cycles of consecutive lengths. Bull. Iranian Math. Soc., 48(5):2395-2405, 2022. URL: https://doi.org/10.1007/s41980-021-00644-1.
  16. Longfei Fang, Bing Wang, and Mingqing Zhai. Planar Turán number of intersecting triangles. Discrete Math., 345(5):Paper No. 112794, 10, 2022. URL: https://doi.org/10.1016/j.disc.2021.112794.
  17. Katalin Fazekas, Aina Niemetz, Mathias Preiner, Markus Kirchweger, Stefan Szeider, and Armin Biere. IPASIR-UP: User propagators for CDCL. In Meena Mahajan and Friedrich Slivovsky, editors, The 26th International Conference on Theory and Applications of Satisfiability Testing (SAT 2023), July 04-08, 2023, Alghero, Italy, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. to appear. Google Scholar
  18. Stefan Felsner. Geometric Graphs and Arrangements - Some Chapters from Combinatorial Geometry. Advanced Lectures in Mathematics (ALM). Vieweg+Teubner, 2004. URL: https://doi.org/10.1007/978-3-322-80303-0.
  19. Stefan Felsner, Hendrik Schrezenmaier, Felix Schröder, and Raphael Steiner. Linear size universal point sets for classes of planar graphs, 2023. http://doi.org/10.48550/arxiv.2303.00109, to appear in Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023).
  20. Stefan Felsner and William T. Trotter. Posets and planar graphs. Journal of Graph Theory, 49(4):273-284, 2005. URL: https://doi.org/10.1002/jgt.20081.
  21. Johannes K. Fichte, Daniel Le Berre, Markus Hecher, and Stefan Szeider. The silent (r)evolution of SAT. Communications of the ACM, 66(6):64-72, June 2023. URL: https://doi.org/10.1145/3560469.
  22. Martin Gardner. Mathematical games. Sci. Amer., 242(1):22-33B, 1980. Google Scholar
  23. Ellen Gethner. To the Moon and Beyond, pages 115-133. Springer Verlag, 2018. URL: https://doi.org/10.1007/978-3-319-97686-0_11.
  24. Debarun Ghosh, Ervin Győri, Ryan R. Martin, Addisu Paulos, and Chuanqi Xiao. Planar Turán number of the 6-cycle. SIAM J. Discrete Math., 36(3):2028-2050, 2022. URL: https://doi.org/10.1137/21M140657X.
  25. J. E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC '74, pages 172-184. Association for Computing Machinery, 1974. URL: https://doi.org/10.1145/800119.803896.
  26. Joan P. Hutchinson. Some conjectures and questions in chromatic topological graph theory. In Graph theory - favorite conjectures and open problems. 1, Probl. Books in Math., pages 195-210. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-31940-7_12.
  27. Tommy R. Jensen and Bjarne Toft. Graph coloring problems. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York, 1995. A Wiley-Interscience Publication. Google Scholar
  28. Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, pages 85-103. Plenum, New York, 1972. Google Scholar
  29. Markus Kirchweger, Manferd Scheucher, and Stefan Szeider. A SAT attack on Rota’s basis conjecture. In 25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022, volume 236 of LIPIcs, pages 4:1-4:18. Schloss Dagstuhl, 2022. URL: https://doi.org/10.4230/LIPIcs.SAT.2022.4.
  30. Markus Kirchweger and Stefan Szeider. SAT modulo symmetries for graph generation. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021), LIPIcs, pages 39:1-39:17. Dagstuhl, 2021. URL: https://doi.org/10.4230/LIPIcs.CP.2021.34.
  31. Jacek P. Kukluk, Lawrence B. Holder, and Diane J. Cook. Algorithm and experiments in testing planar graphs for isomorphism. Journal of Graph Algorithms and Applications, 8(3):313-356, 2004. URL: https://doi.org/10.7155/jgaa.00094.
  32. Yongxin Lan, Yongtang Shi, and Zi-Xia Song. Extremal H-free planar graphs. Electron. J. Combin., 26(2):Paper No. 2.11, 17, 2019. URL: https://doi.org/10.37236/8255.
  33. Anthony Mansfield. Determining the thickness of graphs is NP-hard. Math. Proc. Cambridge Philos. Soc., 93(1):9-23, 1983. URL: https://doi.org/10.1017/S030500410006028X.
  34. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. J. Symbolic Comput., 60:94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
  35. OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published electronically at URL: http://oeis.org.
  36. Steven D. Prestwich. CNF encodings. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, Handbook of Satisfiability - Second Edition, volume 336 of Frontiers in Artificial Intelligence and Applications, pages 75-100. IOS Press, 2021. URL: https://doi.org/10.3233/FAIA200985.
  37. Gerhard Ringel. Färbungsprobleme auf Flächen und Graphen, volume 2 of Mathematische Monographien. Berlin: VEB Deutscher Verlag der Wissenschaften, 1959. Google Scholar
  38. Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. The four-colour theorem. J. Combin. Theory Ser. B, 70(1):2-44, 1997. URL: https://doi.org/10.1006/jctb.1997.1750.
  39. Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner. A note on universal point sets for planar graphs. J. Graph Algorithms Appl., 24(3):247-267, 2020. URL: https://doi.org/10.7155/jgaa.00529.
  40. Walter Schnyder. Planar graphs and poset dimension. Order, 5:323-343, 1989. URL: https://doi.org/10.1007/BF00353652.
  41. Walter Schnyder. Embedding planar graphs on the grid. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '90, pages 138-148. Society for Industrial and Applied Mathematics, 1990. URL: https://doi.org/10.5555/320176.320191.
  42. Carsten Sinz. Towards an Optimal CNF Encoding of Boolean Cardinality Constraints. In 11th International Conference on Principles and Practice of Constraint Programming (CP 2005), volume 3709 of Lecture Notes in Computer Science, pages 827-831. Springer Verlag, 2005. Google Scholar
  43. Grigori S. Tseitin. Complexity of a derivation in the propositional calculus. Zap. Nauchn. Sem. Leningrad Otd. Mat. Inst. Akad. Nauk SSSR, 8:23-41, 1968. Russian. English translation in J. Siekmann and G. Wrightson (eds.) Automation of Reasoning. Classical Papers on Computer Science 1967-1970, Springer Verlag, 466-483, 1983. Google Scholar
  44. Paul Turán. Eine Extremalaufgabe aus der Graphentheorie. Középiskolai Matematikai és Fizikai Lapok, 48:436-452, 1941. Google Scholar
  45. Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2nd edition, 2000. Google Scholar
  46. Hassler Whitney. Non-separable and planar graphs. Proceedings of the National Academy of Sciences of the United States of America, 17(2):125-127, 1931. URL: http://www.jstor.org/stable/86196.
  47. Stanley G. Williamson. Depth-First Search and Kuratowski Subgraphs. Journal of the ACM, 31(4):681-693, 1984. URL: https://doi.org/10.1145/1634.322451.
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact