Abstract :

"A $k$-dimensional box, or ""$k$-box"" for short, is the Cartesian product of $k$ closed intervals on the real line. For example, a $2$-box is an axis-parallel rectangle on the plane and a $3$-box is a cuboid in space with its edges parallel to the axes. The boxicity of a graph $G$ is the minimum integer $k$ such that each vertex of $G$ can be assigned a $k$-box in such a way that two vertices of $G$ are adjacent if and only if their corresponding $k$-boxes intersect. It can be easily seen that the graphs of boxicity $1$ form exactly the well-known class of interval graphs. In this talk, we shall discuss some basic results about the boxicity of graphs. "