  Higher-dimensional orthogonal packing problems have a wide range of practical
applications, including packing, cutting, and scheduling. Previous efforts for
exact algorithms have been unable to avoid structural problems that appear for
instances in two- or higher-dimensional space. We present a new approach for
modeling packings, using a graph-theoretical characterization of feasible
packings. Our characterization allows it to deal with classes of packings that
share a certain combinatorial structure, instead of having to consider one
packing at a time. In addition, we can make use of elegant algorithmic
properties of certain classes of graphs. This allows our characterization to be
the basis for a successful branch-and-bound framework.
  This is the first in a series of papers describing new approaches to
higher-dimensional packing.
