Encyclopedia

Cubicity

Graph invariant defined from axis-parallel unit cubes

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated August 27, 2026

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.

01Definition

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

The cubicity of a graph $G$ , denoted by $\operatorname {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, $\mathrm {E} ^{k}$ .

For $k\geq 1$ , a graph $G$ can have such a representation in $\mathrm {E} ^{k}$ 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.

02Relations to certain graph classes, upper bound

For a graph $G$ , $\operatorname {cub} (G)=0$ if and only if $G$ is complete.

For a graph $G$ , $\operatorname {cub} (G)=1$ if and only if $G$ is a unit interval graph that is not complete.

For $n\in \mathbb {N} ^{*}$ , $\operatorname {cub} (K_{1,n})=\lfloor \log _{2}(2n-1)\rfloor$ , where $K_{1,n}$ denotes the star graph, a tree with one internal vertex and $n$ leaves, and where $\lfloor \cdot \rfloor$ denotes the floor function.

For $p\in \mathbb {N} ^{*}$ , $\operatorname {cub} (K_{p(2)})=p$ , where $K_{p(2)}$ denotes the complete multipartite graph with $p$ parts of cardinal $2$ .

For a graph $G$ on $n$ vertices, $\operatorname {cub} (G)\leq \lfloor 2n/3\rfloor$ . Moreover, this upper bound is best possible in terms of $n$ .

03Relations to other graph dimensions

Relations to boxicity: bounds

The cubicity of a graph $G$ is closely related to its boxicity, denoted by $\operatorname {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., $~\operatorname {box} (G)\leq \operatorname {cub} (G).$

In the other direction, it can be shown that for a graph $G$ on $n$ vertices, $~\operatorname {cub} (G)\leq \lceil \log _{2}n\rceil \operatorname {box} (G),~$ where $\lceil \cdot \rceil$ denotes the ceiling function. Moreover, this upper bound is tight.

Relations to sphericity

The sphericity of a graph $G,$ denoted by $\operatorname {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, $K_{1,5},$ is an example: $~\operatorname {cub} (K_{1,5})=3>\operatorname {sph} (K_{1,5})=2.$

In the other direction, graphs $G$ can be constructed so that $~\operatorname {sph} (G)>\operatorname {cub} (G)=k,~$ for $k\in \{2,3\}.$

Watch videos about CubicityExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Cubicity”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

A graph with cubicity 2.svg by Khmccabe, CC BY-SA 4.0
Indifference graph = unit interval graph.svg by JavBol, CC BY-SA 4.0

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.