Cubicity

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.^[1] 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 an intersection graph of axis-parallel rectangles in Euclidean space.^[2]

This article only considers simple, undirected graphs, with finite and non-empty vertex sets.^[3][4]

The cubicity of a graph ${\displaystyle G}$, denoted by ${\displaystyle \operatorname {cub} (G)}$, is the smallest integer ${\displaystyle n}$ such that ${\displaystyle G}$ can be realized as the intersection graph of axis-parallel closed unit ${\displaystyle n}$-cubes in ${\displaystyle n}$-dimensional Euclidean space.^[5][6][7]

The cubicity of a complete graph is defined to be zero.^[8]
Moreover, ${\displaystyle \operatorname {cub} (G)=0}$ iff ${\displaystyle G}$ is complete.^[9]

The cubicity of a graph ${\displaystyle G}$ is closely related to its boxicity, denoted by ${\displaystyle \operatorname {box} (G)}$. The definition of boxicity is essentially the same as that of cubicity, except in terms of using axis-parallel rectangles instead of axis-parallel unit cubes. Since a cube is a special case of a rectangle, the cubicity of a graph ${\displaystyle G}$ is always an upper bound for its boxicity, i.e., ${\displaystyle \operatorname {box} (G)\leq \operatorname {cub} (G)}$. In the other direction, it can be shown that for any graph ${\displaystyle G}$ on ${\displaystyle n}$ vertices, ${\displaystyle \operatorname {cub} (G)\leq \lceil \log _{2}n\rceil \operatorname {box} (G)}$, where ${\displaystyle \lceil x\rceil }$ is the ceiling function, i.e., the smallest integer greater than or equal to ${\displaystyle x}$. Moreover, this upper bound is tight.^[10]