Boxicity

In the mathematical field of graph theory, the boxicity of a graph is a graph invariant defined to be the minimum dimension of Euclidean space required to represent the graph as an intersection graph of axis-parallel closed boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and these boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices.

Boxicity was introduced by Fred S. Roberts in 1969.

Examples

The figure above shows a graph with six vertices, and a representation of this graph as an intersection graph of six axis-parallel rectangles (two-dimensional boxes) on the Euclidean plane. This graph cannot be represented as an intersection graph of boxes in any lower dimension, so its boxicity is two.

Example of an interval graph with boxicity one

The second figure shows a graph with seven vertices, and a representation of this graph as an intersection graph of seven intervals (one-dimensional boxes) on the real number line. This graph cannot be represented as an intersection graph of boxes in Template:Math-space = Template:Math}, so its boxicity is one.

Relation to certain graph classes

This article only considers simple, finite, undirected graphs.

Template:Harvtxt showed that the graph with Template:Math vertices formed by removing a perfect matching from a complete graph on Template:Math vertices has boxicity exactly Template:Mvar: each pair of disconnected vertices must be represented by boxes that are separated in a different dimension than each other pair. A box representation of this graph with dimension exactly Template:Mvar can be found by thickening each of the Template:Math facets — these are Template:Math-cubes — of an Template:Mvar-dimensional hypercube into an Template:Mvar-box. Because of these results, this graph has been called the Roberts graph, although it is better known as the cocktail party graph and it can also be understood as the Turán graph Template:Math.

The boxicity of a complete graph is defined to be zero.
Moreover, Template:Math iff Template:Mvar is complete.

A graph has boxicity at most one if and only if it is an interval graph; the boxicity of an arbitrary graph Template:Mvar is also the minimum number of interval graphs on the same set of vertices such that the intersection of the edge sets of the interval graphs is Template:Mvar. Every outerplanar graph has boxicity at most two, and every planar graph has boxicity at most three.

If a bipartite graph has boxicity two, then it can be represented as an intersection graph of axis-parallel line segments in the plane (such a graph has grid dimension one).

Template:Harvtxt proved that the boxicity of a bipartite graph Template:Mvar is within a factor Template:Math of the order dimension of the height-two partially ordered set associated to Template:Mvar as follows: the set of minimal elements corresponds to one partite set of Template:Mvar, the set of maximal elements corresponds to the second partite set of Template:Mvar, and two elements are comparable if the corresponding vertices are adjacent in Template:Mvar. Equivalently, the order dimension of a height-two partially ordered set Template:Mvar is within a factor Template:Math of the boxicity of the comparability graph of Template:Mvar (which is bipartite, since Template:Mvar has height two).

Algorithmic results

Many graph problems can be solved or approximated more efficiently for graphs with bounded boxicity than they can for other graphs; for instance, the maximum clique problem can be solved in polynomial time for graphs with bounded boxicity. For some other graph problems, an efficient solution or approximation can be found if a low-dimensional box representation is known. However, finding such a representation may be difficult: it is NP-complete to test whether the boxicity of a given graph is at most some given value Template:Mvar, even for Template:Math. Template:Harvtxt describe algorithms for finding representations of arbitrary graphs as intersection graphs of boxes, with a dimension that is within a logarithmic factor of the maximum degree of the graph; this result provides an upper bound on the graph's boxicity.

Despite being hard for its natural parameter, boxicity is fixed-parameter tractable when parameterized by the vertex cover number of the input graph.

Bounds

For any graph $G$, $\mathrm{box}(G)\le \mathrm{tw}(G)+2$, where $\mathrm{tw}(G)$ denotes the treewidth of $G$.

If a graph $G$ has $m$ edges, then $\mathrm{box}(G)=O\left(\sqrt{m\log m}\right)$.

If a graph $G$ is $k$-degenerate (with $k\ge 2$) and has $n$ vertices, then $\mathrm{box}(G)\le (k+2)\lceil 2\mathrm{e}\log n\rceil$, where $\lceil \cdot \rceil$ denotes the ceiling function.

If a graph $G$ has no complete graph on $t$ vertices as a minor, then $\mathrm{box}(G)=O(t^2\log t)$, while there are graphs with no complete graph on $t$ vertices as a minor, and with $\mathrm{box}(G)=\mathrm{\Omega }(t\cdot \sqrt{\log t})$. In particular, any graph $G$ has $\mathrm{box}(G)=O(\mu (G{)}^2\log \mu (G))$, where $\mu (G)$ denotes the Colin de Verdière invariant of $G$.

Related graph invariants

• Cubicity is defined in the same way as boxicity but with axis-parallel unit hypercubes instead of axis-parallel hyperrectangles. Boxicity is a generalization of cubicity.
• Sphericity is defined in the same way as boxicity but with congruent spheres.

References

• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.