Metraipolis › archive › dc_ee88a1ff6dcd
Geometric Graph Representations via Compact SAT Encodings — arXiv:2610.22241
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.22241
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:34:27.781Z
- SHA-256 of the archived text
d797a26196242ab501e6540d8ef666e9340d4f593c9d2dcd9f4117294103457e- Stable URL of this page
https://metraipolis.com/documento/dc_ee88a1ff6dcd
How to cite
Geometric Graph Representations via Compact SAT Encodings — arXiv:2610.22241 — arXiv (en), https://arxiv.org/abs/2610.22241 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ee88a1ff6dcd (Metraipolis archive dc_ee88a1ff6dcd, sha256 d797a26196242ab501e6540d8ef666e9340d4f593c9d2dcd9f4117294103457e)
BibTeX
@misc{dcee88a1ff6dcd,
title = {Geometric Graph Representations via Compact SAT Encodings — arXiv:2610.22241},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.22241},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ee88a1ff6dcd; sha256 d797a26196242ab501e6540d8ef666e9340d4f593c9d2dcd9f4117294103457e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.22241. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $n$-vertex graph and target dimension $d$, our boxicity encoding uses $O(n^2d)$ variables and $O(n^3d)$ clauses, both linear in $d$. 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 $K(n,k)$ with $k\ge3$ and $n\ge2k+1$ contains an induced Desargues graph. The resulting lower bound, together with an explicit three-dimensional representation of $K(7,3)$, establishes $\operatorname{boxicity}(K(7,3))=3$. This disproves the conjecture of Caoduro and Sebo that $\operatorname{boxicity}(K(n,k))=n-k$ for all $k\ge3$ and $n\ge2k+1$.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Computational Geometry (cs.CG) ; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Logic in Computer Science (cs.LO); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.22241 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:50:47.623Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).