# 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. – hardmath Nov 18 '16 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. – user340082710 Nov 18 '16 at 23:15
• Certainly. That would be great. – user340082710 Nov 18 '16 at 23:19
• An octahedron looks like a winner, aka T(6,3) looking at the boxicity wikipedia article and the Turan Graph page. – Dr Xorile Nov 18 '16 at 23:34