Boxicity of graphs

the graph with vertices corresponding to the sets in S and with edges such
that two vertices are adjacent if and only if the sets corresponding to them
have a non-empty intersection. Thus, if S is a collection of closed intervals
on the real line, G(S) is an interval graph. We get higher dimensional
analogues of interval graphs if we replace the set S with ``boxes'' or tuples
of intervals. For example, an ordered pair of intervals (a 2-dimensional box)
would be a rectangle on the plane. The ``boxicity'' of a graph G, or box(G), is
the minimum integer k such that G is the intersection graph of k-dimensional
boxes. Thus graphs with boxicity 1 are the interval graphs.
For any graph G on n vertices, box(G)<= n/2.
The concept of boxicity finds application in ecology and in operations
research.

We show that for a graph G on n vertices with maximum degree D,
box(G)<= 2 D^2 + 2.