4
$\begingroup$

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:

triangular antiprism, boxicity 3

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

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

octahedron

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:

Box representation

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.