Boxicity and Maximum degree

L. Sunil Chandran, Mathew C. Francis, Naveen Sivadasan

Published 2006-10-08Version 1

An axis-parallel $d$--dimensional box is a Cartesian product $R_1 \times R_2 \times ... \times R_d$ where $R_i$ (for $1 \le i \le d$) is a closed interval of the form $[a_i, b_i]$ on the real line. For a graph $G$, its \emph{boxicity} $\boxi(G)$ is the minimum dimension $d$, such that $G$ is representable as the intersection graph of (axis--parallel) boxes in $d$--dimensional space. The concept of boxicity finds applications in various areas such as ecology, operation research etc. We show that for any graph $G$ with maximum degree $\Delta$, $\boxi(G) \le 2 \Delta^2 + 2$. That the bound does not depend on the number of vertices is a bit surprising considering the fact that there are highly connected bounded degree graphs such as expander graphs. Our proof is very short and constructive. We conjecture that $\boxi(G)$ is $O(\Delta)$.