Approximating the Cubicity of Trees

Jasine Babu, Manu Basavaraju, L Sunil Chandran +2

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 inters…