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]
Let be a graph. Then the cubicity of , denoted by , is the smallest integer such that can be realized as an intersection graph of axis-parallel unit cubes in -dimensional Euclidean space. [2]
The cubicity of a graph is closely related to the boxicity of a graph, denoted . 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 on vertices, the inequality , where is the ceiling function, i.e., the smallest integer greater than or equal to . [3]
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]
Let be a graph. Then the cubicity of , denoted by , is the smallest integer such that can be realized as an intersection graph of axis-parallel unit cubes in -dimensional Euclidean space. [2]
The cubicity of a graph is closely related to the boxicity of a graph, denoted . 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 on vertices, the inequality , where is the ceiling function, i.e., the smallest integer greater than or equal to . [3]