Cubicity Explained

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 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

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

The cubicity of a graph is closely related to the boxicity of a graph, denoted

\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 G on m vertices, the inequality \operatorname{cub} (G) \leq \lceil log _{2} n \rceil \operatorname{box} (G) , where \lceil x \rceil is the ceiling function, i.e., the smallest integer greater than or equal to 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 . en . 35 . 3 . 309–318 . 10.1016/0095-8956(83)90057-6 . 0095-8956.
3. Sunil Chandran . L. . Ashik Mathew . K. . 2009-04-28 . An upper bound for Cubicity in terms of Boxicity . Discrete Mathematics . en . 309 . 8 . 2571–2574 . 10.1016/j.disc.2008.04.011 . 7837544 . 0012-365X. math/0605486 .