Computing a minimum-dilation spanning tree is NP-hard

Abstract

In a geometric network G=(S,E), the graph distance between two vertices u, v∈S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which graph distance differs from the Euclidean distance between every pair of vertices. We show that given a set S of n points and a dilation $\delta$>1, it is NP-hard to determine whether a spanning tree of S with dilation at most $\delta$ exists.