On the cubicity of bipartite graphs

A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R1×R2×⋯×Rk, where each Ri is a closed interval on the real line of the form [ai,ai+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph.It is known that for a graph G, . Recently it has been shown that for a graph G, cub(G)⩽4(Δ+1)lnn, where n and Δ are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G=(A∪B,E) with |A|=n1, |B|=n2, n1⩽n2, and Δ′=min{ΔA,ΔB}, where ΔA=maxa∈Ad(a) and ΔB=maxb∈Bd(b), d(a) and d(b) being the degree of a and b in G, respectively, cub(G)⩽2(Δ′+2)⌈lnn2⌉. We also give an efficient randomized algorithm to construct the cube representation of G in 3(Δ′+2)⌈lnn2⌉ dimensions. The reader may note that in general Δ′ can be much smaller than Δ.