Cubicity

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

The cubicity of a graph is closely related to the boxicity of a graph, denoted ${\displaystyle \operatorname {box} (G)}$. The definition of boxicity is essentially the same as cubicity, except in terms of using axis-parallel rectangles instead of cubes. Since a cube is a special case of a rectangle, the cubicity of a graph is always an upper bound for the boxicity of a graph. In the other direction, it can be shown that for any graph ${\displaystyle G}$ on ${\displaystyle m}$ vertices, the inequality ${\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}$.[3]