Sublinear Approximation Algorithms for Boxicity and Related Problems

Abhijin Adiga, Jasine Babu, L. Sunil Chandran

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes in ${\mathbb{R}}^k$. Cubicity is a variant of box…