2007/03/06 by Otfried Cheong, Cheong, Otfried, Herman Haverkort +3
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.cs/0703023
arxiv created 2007/03/06 · openalex publication_date 2007/03/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
In a geometric network G = (S, E), the graph distance between two vertices u, v in S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation delta > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most delta exists.