An axis-parallel b-dimensional box is a Cartesian product R
1×R
2××R
b where each R
i (for 1≤i≤b) is a closed interval of the form [a
i,b
i] on the real line. The boxicity of any graph 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×R
2××R
b, where each R
i (for 1≤i≤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 ). In this paper we prove that , where n is the number of vertices in the graph. We also show that this upper bound is tight.
Some immediate consequences of the above result are listed below:
1. Planar graphs have cubicity at most 3log2n.
2. Outer planar graphs have cubicity at most 2log2n.
3. Any graph of treewidth tw has cubicity at most (tw+2)log2n. Thus, chordal graphs have cubicity at most (ω+1)log2n and circular arc graphs have cubicity at most (2ω+1)log2n, where ω is the clique number.
The above upper bounds are tight, but for small constant factors.
