pipette
ESEspañol

Geometric Graph Representations via Compact SAT Encodings

L. Sunil Chandran, Rishikesh Gajjala, Suraj Kumar Sahoo, Aatman Supkar

Preprint

In the authors' words

We present compact SAT encodings and certifying exact solvers for boxicity and cubicity. The boxicity of a graph is the minimum dimension in which it is the intersection graph of axis-aligned boxes; cubicity is defined analogously using unit cubes. Grid-based formulations face a geometric discretization bottleneck, growing rapidly with the target dimension. We avoid this bottleneck by encoding the total order of interval endpoints in each coordinate. For an -vertex graph and target dimension , our boxicity encoding uses variables and clauses, both linear in . Requiring the left- and right-endpoint orders to agree yields a cubicity encoding of the same asymptotic size. Satisfying models are decoded into independently checked geometric representations, while unsatisfiable instances used as lower-bound evidence carry mechanically verified DRAT certificates. In a controlled evaluation with 186 trials per encoding on standard and structured graph families, the order encoding solves 96.8% of trials, compared with 71.0% for the known grid formulation, and reduces mean PAR-2 time from 178.21 to 21.70 seconds. The pipeline also certifies exact values for several named graphs. We turn one such value into a reusable obstruction by proving that every Kneser graph with and contains an induced Desargues graph. The resulting lower bound, together with an explicit three-dimensional representation of , establishes . This disproves the conjecture of Caoduro and Sebo that for all and .

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: To appear in ALENEX 2027