An upper bound for Cubicity in terms of Boxicity

Abstract

An axis-parallel b-dimensional box is a Cartesian product $R_1\times R_2\times ...\times R_b$ where each $R_i$ (for $1\le i\le b$) is a closed interval of the form $[a_i,b_i]$ on the real line. The boxicity of any graph $G$, box(G) is the minimum positive integer b such that G can be represented as the intersection graph of axis parallel b-dimensional boxes. A b-dimensional cube is a Cartesian product $R_1\times R_2\times ...\times R_b$, where each $R_i$ (for $1\le i\le b$) is a closed interval of the form [$a_i$,$a_i$+1] on the real line. When the boxes are restricted to be axis-parallel cubes in b-dimension, the minimum dimension b required to represent the graph is called the cubicity of the graph (denoted by cub(G)). In this paper we prove that $cub(G)\leq \lceil \log n \rceil \boxi(G)$} where n is the number of vertices in the graph. This upper bound is tight.

6 pages, 0 figures

Cited by in corpus (1)

• Representing graphs as the intersection of axis-parallel cubes