Boxicity

In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.

That is, there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices.

This graph cannot be represented as an intersection graph of boxes in any lower dimension, so its boxicity is two.

Roberts (1969) showed that the graph with 2n vertices formed by removing a perfect matching from a complete graph on 2n vertices has boxicity exactly n: 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 n can be found by thickening each of the 2n facets of an n-dimensional hypercube into a box.

[3] If a bipartite graph has boxicity two, it can be represented as an intersection graph of axis-parallel line segments in the plane.

[4] Adiga, Bhowmick & Chandran (2011) proved that the boxicity of a bipartite graph G is within of a factor 2 of the order dimension of the height-two partially ordered set associated to G as follows: the set of minimal elements corresponds to one partite set of G, the set of maximal elements corresponds to the second partite set of G, and two elements are comparable if the corresponding vertices are adjacent in G. Equivalently, the order dimension of a height-two partially ordered set P is within a factor 2 of the boxicity of the comparability graph of P (which is bipartite, since P has height two).

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.

[5] For some other graph problems, an efficient solution or approximation can be found if a low-dimensional box representation is known.

[6] 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 K, even for K = 2.

[7] Chandran, Francis & Sivadasan (2010) 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.

denotes the Colin de Verdière invariant of G.