{"id":"arxiv/2610.22241","url":"https://arxiv.org/abs/2610.22241","tags":["cs.CG","cs.DM","cs.DS","cs.LO","math.CO"],"score":0,"title":"Geometric Graph Representations via Compact SAT Encodings","domain":"cs.CG","source":"arxiv","authors":["L. Sunil Chandran","Rishikesh Gajjala","Suraj Kumar Sahoo","Aatman Supkar"],"reviews":0,"subject":"cs.CG","summary":"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$.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}