Geometric representation of graphs in low dimension

L. Sunil Chandran, Mathew C Francis, Naveen Sivadasan

We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in $1.5(\Delta +2)\ln n$ dimensions, where $\Delta$ is the maximum degree of G. We…