A linear-time approximation algorithm for the minimum-length geometric embedding of trees

In this paper, we study the problem of computing a geometric embedding of a tree onto a point set in the Euclidean plane such that the total edge length of the embedding is minimum. We present a linear-time O(Δph(T))-approximation algorithm, where Δ and ph(T) denote the maximum node-degree and the path height of the input tree T, respectively. The previous best result in the literature has O(nlog⁡log⁡n) time-complexity and O(Δlog2⁡n) approximation factor. We show that ph(T) is less than log2⁡n for any n-node tree T. The problem is a generalization of the Euclidean travelling salesman problem, which is a well-known NP-hard problem.