SAT-Based Generation of Planar Graphs

Markus Kirchweger, Manfred Scheucher, Stefan SzeiderSAT 2023 · DOI

TL;DR

This paper introduces a novel SAT-based approach for generating planar graphs, a fundamental problem in graph theory. By integrating dynamic symmetry breaking with various planarity testing criteria, the authors efficiently enumerate and analyze planar graphs, leading to new insights in combinatorial problems like planar Turán numbers and the Earth-Moon problem.

What Problem Does This Paper Address?

Generating all graphs with a specific property, like planarity, is a challenging task in combinatorics. Traditional methods often struggle with the sheer number of possible graphs and the inherent symmetries that lead to redundant computations. While SAT solvers are powerful tools for constraint satisfaction, directly encoding graph properties and ensuring symmetry breaking for generation has been an open area. This paper tackles the problem of efficiently generating planar graphs by leveraging SAT Modulo Symmetry (SMS) and developing new SAT encodings for planarity, aiming to overcome the scalability issues of existing methods.

Methods

The core of this work lies in developing and comparing three distinct SAT encodings for planarity within the SMS framework:

  • Kuratowski's Theorem (Lazy Encoding): This approach uses Kuratowski's theorem (a graph is planar iff it doesn't contain $K_{3,3}$ or $K_5$ as a topological minor) to exclude non-planar graphs. When a partial graph assignment is found to contain such a minor, a clause is added to the SAT solver to prevent further exploration of that branch. This is a "lazy" approach as it reacts to violations.
  • Schnyder Orders (Eager Encoding): This method leverages Schnyder's theorem, which states that a graph is planar if and only if its incidence order dimension is at most 3. The encoding directly enforces the existence of three specific partial orders (Schnyder orders) that characterize planar graphs. This is an "eager" approach as it builds planarity into the encoding from the start.
  • Universal Sets (Eager Encoding): This encoding relies on the concept of universal point sets, which are sets of points in the plane onto which any planar graph can be embedded with straight-line edges. The SAT encoding attempts to map vertices to these points and ensures that no edges cross. This approach is also "eager."

The authors also extend the SMS framework to handle directed graphs, which is crucial for problems like the Earth-Moon problem.

Datasets

The paper doesn't use traditional "datasets" in the machine learning sense. Instead, it focuses on generating and analyzing combinatorial objects (planar graphs) for specific problems:

  • Planar Turán Numbers: The authors compute exact values for planar Turán numbers $exp(n, C_k)$ for small $n$ and $k=4, 5$.
  • Earth-Moon Problem: They investigate the chromatic number of biplanar graphs for various numbers of vertices.
  • Integer Sequences: They verify and extend sequences from the Online Encyclopedia of Integer Sequences (OEIS) related to planar graph enumeration.

Key Insights and Ideas

  • Symmetry Breaking is Crucial: The paper strongly emphasizes that dynamic symmetry breaking (via SMS) is essential for making SAT-based graph generation scalable. Without it, the search space explodes.
  • Lazy vs. Eager Encodings: The comparison between the Kuratowski-based (lazy) and Schnyder-order-based (eager) encodings reveals that the lazy approach is significantly more efficient, especially for unsatisfiable instances. This is because it can prune large parts of the search space early.
  • Directed Graphs for Biplanar Problems: Representing biplanar graphs as directed graphs is a clever way to leverage existing SMS machinery for directed graphs, enabling new insights into problems like the Earth-Moon problem.
  • Versatility of SMS: The framework's ability to handle various planarity criteria and be extended to digraphs highlights its broad applicability for combinatorial enumeration.
  • OEIS as a Benchmark: Using OEIS sequences provides a systematic way to test and validate the performance of graph generation tools, and the authors demonstrate how SMS can extend known sequences.

Key Results

  • Planar Turán Numbers: The paper computes exact values for $exp(n, C_4)$ and $exp(n, C_5)$ for $n$ up to 18 and 18 respectively, providing new results and confirming existing bounds.
  • Earth-Moon Problem: They prove that all biplanar graphs on fewer than 13 vertices are 9-colorable. They also show that a specific candidate graph for chromatic number 10 is not biplanar.
  • OEIS Sequences: The authors successfully verified and extended several OEIS sequences related to planar graph enumeration, demonstrating the practical utility of their approach. For instance, they extended sequences for planar graphs with even degrees and planar graphs with minimum degrees.
  • Performance Comparison: The Kuratowski-based encoding consistently outperformed the Schnyder-order-based encoding, especially for unsatisfiable cases, by orders of magnitude in some instances. The universal set encoding was found to be too inefficient for practical use beyond very small graphs.

Limitations and Future Work

  • Universal Set Encoding Inefficiency: The authors acknowledge that the universal set encoding is computationally expensive and only practical for very small graphs ($n < 11$).
  • Symmetry Breaking for Biplanar Graphs: While the directed graph approach for biplanar graphs is effective, the authors note that there's still room for improvement in handling isomorphic decompositions and isomorphic partitions. They plan to design a version of SMS to avoid these isomorphic copies.
  • Outerplanar Graphs: They suggest exploring adaptations of the Kuratowski and Schnyder encodings for outerplanar graphs as an interesting future application.
  • Planar Graph Canonization: The paper mentions that a polynomial-time canonization algorithm for planar graphs exists and suggests translating it into a SAT encoding to see if it outperforms general symmetry breaking.

Summary updated

BibTeX
@inproceedings{kirchweger2023sat,
  author = {Markus Kirchweger and Manfred Scheucher and Stefan Szeider},
  title = {{SAT-Based Generation of Planar Graphs}},
  booktitle = {SAT},
  year = {2023},
  doi = {10.4230/lipics.sat.2023.14},
}
Figure