Cubicity

A graph with cubicity 2, realized as the intersection graph of axis-parallel unit 2-cubes, i.e. axis-parallel unit squares, in the plane.

In the mathematical field of graph theory, cubicity is a graph invariant defined to be the smallest dimension such that a graph can be realized as the intersection graph of axis-parallel unit cubes in Euclidean space. Cubicity was introduced by Fred S. Roberts in 1969, along with a related invariant called boxicity that considers the smallest dimension needed to represent a graph as the intersection graph of axis-parallel rectangles in Euclidean space.

An indifference graph with cubicity 1, realized as the intersection graph of unit 1-cubes, i.e. unit intervals, on the real number line.

Definition

This article only considers simple, undirected graphs, with finite and non-empty vertex sets.

The cubicity of a graph G, denoted by cub⁡(G), is the smallest integer k such that G can be represented as the intersection graph of axis-parallel closed unit k-cubes in k-dimensional Euclidean space, Ek.

For k≥1, a graph G can have such a representation in Ek if and only if G is the intersection of k indifference graphs on the same vertex set as G.

The cubicity of a complete graph is defined to be zero.

Relations to certain graph classes, upper bound

For a graph G, cub⁡(G)=0 if and only if G is complete.

For a graph G, cub⁡(G)=1 if and only if G is a unit interval graph that is not complete.

For n∈ℕ∗, cub⁡(K1,n)=⌊log2(2n−1)⌋, where K1,n denotes the star graph, a tree with one internal vertex and n leaves, and where ⌊⋅⌋ denotes the floor function.

For p∈ℕ∗, cub⁡(Kp(2))=p, where Kp(2) denotes the complete multipartite graph with p parts of cardinal 2.

For a graph G on n vertices, cub⁡(G)≤⌊2n/3⌋. Moreover, this upper bound is best possible in terms of n.

Relations to other graph dimensions

Relations to boxicity: bounds

The cubicity of a graph G is closely related to its boxicity, denoted by box⁡(G). The definition of boxicity is essentially the same as that of cubicity, but with axis-parallel boxes instead of axis-parallel unit cubes.

Since a cube is a special case of a box, the cubicity of a graph G is always an upper bound for its boxicity, i.e.,  box⁡(G)≤cub⁡(G).

In the other direction, it can be shown that for a graph G on n vertices,  cub⁡(G)≤⌈log2n⌉box⁡(G),  where ⌈⋅⌉ denotes the ceiling function. Moreover, this upper bound is tight.

Relations to sphericity

The sphericity of a graph G, denoted by sph⁡(G), is defined in the same way as cubicity but with congruent spheres instead of axis-parallel unit cubes.

For certain graphs, cubicity exceeds sphericity; the five-pointed star, K1,5, is an example:  cub⁡(K1,5)=3>sph⁡(K1,5)=2.

In the other direction, graphs G can be constructed so that  sph⁡(G)>cub⁡(G)=k,  for k∈{2,3}.