  Cubicity of a graph $G$ is the smallest dimension $d$, for which $G$ is a
unit disc graph in ${\mathbb{R}}^d$, under the $l^\infty$ metric, i.e. $G$ can
be represented as an intersection graph of $d$-dimensional (axis-parallel) unit
hypercubes. We call such an intersection representation a $d$-dimensional cube
representation of $G$. Computing cubicity is known to be inapproximable in
polynomial time, within an $O(n^{1-\epsilon})$ factor for any $\epsilon >0$,
unless NP=ZPP.
  In this paper, we present a randomized algorithm that runs in polynomial time
and computes cube representations of trees, of dimension within a constant
factor of the optimum. It is also shown that the cubicity of trees can be
approximated within a constant factor in deterministic polynomial time, if the
cube representation is not required to be computed. As far as we know, this is
the first constant factor approximation algorithm for computing the cubicity of
trees. It is not yet clear whether computing the cubicity of trees is NP-hard
or not.
