Cubicity

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

In graph theory, cubicity is a graph invariant defined to be the smallest dimension such that a graph can be realized as an 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 an intersection graph of axis-parallel rectangles in Euclidean space. ^[1]

Definition

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 by ${\displaystyle \operatorname {box} (G)}$. The definition of boxicity is essentially the same as 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 is always an upper bound for the boxicity of a graph, 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}$. ^[3]

References

1. Roberts, F. S. (1969). On the boxicity and cubicity of a graph. In W. T. Tutte (Ed.), Recent Progress in Combinatorics (pp. 301–310). San Diego, CA: Academic Press. ISBN 978-0-12-705150-5
2. Fishburn, Peter C. (1983-12-01). "On the sphericity and cubicity of graphs" . Journal of Combinatorial Theory, Series B. 35 (3): 309–318. doi:10.1016/0095-8956(83)90057-6. ISSN   0095-8956.
3. Chandran, L. Sunil; Mathew, K. Ashik (2009-04-28). "An upper bound for Cubicity in terms of Boxicity". Discrete Mathematics. 309 (8): 2571–2574. arXiv: math/0605486 . doi:10.1016/j.disc.2008.04.011. ISSN   0012-365X. S2CID   7837544.