### Example: Not recognizing intersection graphs of boxes in
**R**^{2}

As for many geometric intersection models, the first step,
finding sufficiently many star graphs, is easy
for intersection graphs of boxes in **R**^{d}.
We only have to find the cliques. The problem is the layout step,
where we have to place the cliques on the plane in a certain way.
After the placement has been done, for every vertex *x* of
*G*, the (points corresponding to the) cliques containing *x* generate
a smallest axis-parallel rectangle, which we denote by
*S*_{x}.
These rectangles should obey:

- for every vertex
*x* of *G*, all
(points corresponding to)
cliques in *S*_{x} must contain *x*, and
- if
*S*_{x} and *S*_{y} intersect,
then they have some
(point corresponding to a) clique in common.

Actually recognizing intersection graphs of *d*-dimensional boxes is
NP-complete
for *d => 2*
[K94] for *d=2*,
[Y82] for *d
3*).
Therefore this layout problem must be NP-complete too.

Erich Prisner

made on January 12, 1999