Y. Bartal has studied a related problem of embedding metric spaces to *hierarchically separated trees*. With $1 < \mu$ being a fixed real number, a $\mu$-HST is equivalent to the set of corners of a rectangle whose edges are of length $c, c\mu^{-1}, c\mu^{-2}, \dots, c\mu^{1-D}$ with the $l_\infty$-metric. That is, if you think of the space as the set of bit sequences of length $D$, the distance of two sequences is $c\mu^{-j}$ if they first differ in bit $j$.

Now in your question you didn't ask for $\infty$-metric, but for this set of points, it doesn't really matter which metric you take because the distortion between this and either the $l_1$ or $l_2$ metric is bounded by a constant (if you fix $\mu$ but $D$ can vary).

(This metric can be considered a graph metric on a special tree, that is, one where the points are some (but not necessarily all) vertexes of a tree graph with weighted edges, and the distance is the shortest path. This is where "tree" in the name comes from.)

Now Bartal's result in [1] basically says that you can embed any metric space *randomly* to a $\mu$-HST with distortion at most $\mu(2\ln n+2)(1+\log_\mu n)$ where $n$ is the number of points. (Also, this embedding can be computed with a randomized polynomial algorithm.)

For this, you need to know what a distortion $\alpha$ random embedding $f$ means. It means that for any two points $d(x,y) < d(f(x),f(y))$ is always true and that the expected value of $d(f(x),f(y))$ is at most $\alpha d(x,y)$. For many applications, this is just as good as a deterministic embedding with low distortion. In fact, you can make a deterministic embedding with low distortion from it by imagining the metric $d^* $ on the original space where $d^*(x,y) = E(d(f(x), f(y))$, but this notion isn't too useful because the resulting metric does not have nice properties anymore (it's not HST). Indeed, I believe the randomness is essential here as I seem to remember reading somewhere that you can't embed a cycle graph (with equal edge weights) to a tree graph with low distortion.

Anyway, this might not really answer your question. Firstly, $D$ (the number of dimensions of the rectangle) is not determined in advance, but that's not a real problem because if you have $D$ significantly different distances in the input metric then you need at least that large a $D$ for any embedding; and with this embedding you don't need a $D$ larger than $\log_\mu (\Delta/\delta)$ where $\Delta$ and $\delta$ are the largest and smallest distances in the input. The real problem is that you seem to want to know a deterministic embedding, and the highest possible distortion necessary in that case, which this really doesn't tell. For example, a cycle graph with an even number $n$ of vertexes can of course be embedded isometrically to a cube of dimension $n/2$.

Survey [2] has some more references.

[1]: Yair Bartal, On Approximating Arbitrary Metrics by Tree Metrics. *Annual ACM Symposium on Foundations of Computer Science*, 37 (1996), 184–193.

[2]: Piotr Indyk, Jiří Matoušek, Low-distortion embeddings of finite metric spaces. Chapter 8 in *Handbook of Discrete and Computational Geometry*, ed. Jacob E. Goodman and Joseph O'Rourke, CRC Press, 2004.