The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can be solved optimaly in polynomial time (Chung, [1984]).
So, what about trees in higher (fixed) dimension? To be more precise:
$d$-dimensional Arrangement Problem of Trees:
$\text{Input}: d$, a tree $T=(V,E),$ $|V|=n=a^d$
$\text{Task}$: Find a bijection $b: V\rightarrow\{{1,\ldots,\sqrt[d]{n}\}}^d$, such that
$$\sum_{e=(v,w)\in E}|b(v)-b(w)|_1$$ is minimized.
Can we generalize an algorithm from the linear case, or can we show that this problem is still $NP$-hard? Since both questions seem hard (to me), is there at least a constant factor approximation algorithm (down from $O(\log n)$ for general graphs) for this problem?
Ideas, thoughts or paper recommendations would be appreciated.
