A Constant Factor Approximation Algorithm for Boxicity of Circular Arc Graphs

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 $k$-dimensional axis parallel rectangles in ${\mathbf{R}}^k$. Eq…