The data arrangement problem on regular trees (DAPT) consists in assigning the vertices of a given graph G to the leaves of a d-regular tree T such that the sum of the pairwise distances of all pairs of leaves in T which correspond to edges of G is minimised. This problem is a special case of the generic graph embedding problem and is NP-hard for every fixed $$d\ge 2$$ d ≥ 2 . In this paper we propose construction and local search heuristics for the DAPT and introduce a lower bound for this problem. The analysis of the performance of the heuristics is based on two considerations: (a) the quality of the solutions produced by the heuristics as compared to the respective lower bound (b) for a special class of instances with known optimal solution we evaluate the gap between the optimal value of the objective function and the objective function value attained by the heuristic solution, respectively.