Geometric Graph Representations via Compact SAT Encodings

L. Sunil Chandran, Rishikesh Gajjala, Suraj Kumar Sahoo +1

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 a…