Boxicity and maximum degree

Abstract: A d-dimensional box is a Cartesian product of d closed intervals on the real line. The boxicity of a graph is the minimum dimension d such that it is representable as the intersection graph of d-dimensional boxes. We give a short constructive proof that every graph with maximum degree D has boxicity at most . We also conjecture that the best upper bound is linear in D. [Copyright &y& Elsevier]