An upper bound for Cubicity in terms of Boxicity

An axis-parallel bb-dimensional box is a Cartesian product R1×R2×⋯×RbR1×R2×⋯×Rb where each RiRi (for 1≤i≤b1≤i≤b) is a closed interval of the form [ai,bi][ai,bi] on the real line. The boxicity of any graph GG, box(G) is the minimum positive integer bb such that G can be represented as the intersection graph of axis-parallel bb-dimensional boxes. A bb-dimensional cube is a Cartesian product R1×R2×⋯×RbR1×R2×⋯×Rb, where each RiRi (for 1≤i≤b1≤i≤b) is a closed interval of the form [ai,ai+1][ai,ai+1] on the real line. When the boxes are restricted to be axis-parallel cubes in bb-dimension, the minimum dimension bb required to represent the graph is called the cubicity of the graph (denoted by cub(G)). In this paper we prove that cub(G)≤⌈log2n⌉box(G), where nn 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 3⌈log2n⌉3⌈log2n⌉.2.Outer planar graphs have cubicity at most 2⌈log2n⌉2⌈log2n⌉.3.Any graph of treewidth twtw has cubicity at most (tw+2)⌈log2n⌉(tw+2)⌈log2n⌉. Thus, chordal graphs have cubicity at most (ω+1)⌈log2n⌉(ω+1)⌈log2n⌉ and circular arc graphs have cubicity at most (2ω+1)⌈log2n⌉(2ω+1)⌈log2n⌉, where ωω is the clique number.The above upper bounds are tight, but for small constant factors.