Example: Not recognizing intersection graphs of boxes in R²

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.