Intersection graphs of boxes and cubes

Mathew Francis

Abstract

Let S be a collection of sets. A graph G(V,E) is an intersection graph of sets from S if there exists a function f:V - S such that (u,v)\in E <= f(u) and f(v) have a nonempty intersection.

"Interval graphs" are the intersection graphs of closed intervals on the real line. That is, a closed interval can be mapped to each vertex of such a graph so that two vertices are adjacent if and only if the intervals assigned to them overlap. Interval graphs find application in diverse fields ranging from DNA analysis to process scheduling.

A natural generalization of intervals to higher dimensions is that of "k-dimensional boxes". A k-dimensional box or k-box in short is the Cartesian product R_1 X R_2 X ... X R_k where each R_i is a closed interval. Thus, a 2-box is a rectangle with sides parallel to the axes and a 3-box is an axis-parallel cuboid. If each R_i is of unit length, we say that the k-