# Smallest graph that cannot be represented by the intersection graph of axis-aligned rectangles

Is it known that any outerplanar graph can be represented as the geometric intersection graph of axis-aligned rectangles, while any planar graph can be represented as the intersection graph of axis-aligned boxes in 3d. This is also known as the boxicity of a graph. What is a small example of a graph that has boxicity greater than 2 (i.e cannot be represented by the intersection of axis-aligned rectangles)? I am doing a presentation, and I would like an example to show (to an audience who may not be completely familiar with the area) that these two things are "clearly" different (which is why I need a small graph).

Edit: I don't really need the smallest such graph. I would like one where others can easily convince themselves that it cannot be represented by intersecting rectangles.

Roberts introduced the notion of boxicity in 1969 ( "On the boxicity and cubicity of a graph", in Tutte, W. T., Recent Progress in Combinatorics, Academic Press, pp. 301–310) and showed that "every graph on $n$ vertices has an $⌊n/2⌋$-box and a $⌊2n/3⌋$-cube representation." Thus a minimal example of a graph without representation as the intersection graph of axis-aligned rectangles in the plane (dimension $2$) must have (at least) six vertices.

Roberts gave a family of "tight" examples, often called cocktail party graphs, having $2n$ vertices whose boxicity is exactly $n$. For $n=3$ the graph is that of a triangular antiprism, and so (as a polyhedron) is planar:

• Note that the Wikipedia article describes an example of boxicity $n$ on $2n$ vertices, so the problem becomes bounded by $6$ vertices and twelve edges. Commented Nov 18, 2016 at 18:01
• I guess I don't really need the "smallest" such graph, but I would like one where others can easily convince themselves that it cannot be represented by intersecting rectangles (without really going into a real proof). I just suspect that it will be easier to do so if the graph is small. Commented Nov 18, 2016 at 23:15
• Certainly. That would be great. Commented Nov 18, 2016 at 23:19
• An octahedron looks like a winner, aka T(6,3) looking at the boxicity wikipedia article and the Turan Graph page. Commented Nov 18, 2016 at 23:34

As I mentioned, I think an octahedron works pretty well (no credit to me - just followed the wikipedia links!)

If you take the 4 outer edges and represent them with blue rectangles, and the "top" one with a green edge, you can see that the "bottom" one would need to basically overlap the top one. But if you stretched it up into three dimensions the top and bottom can stack:

(Each vertex represents a box, and the boxes overlaps iff the corresponding vertices share an edge)