2013/05/17 by Vida Dujmović, Pat Morin, Dujmovic, Vida +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Networking and Internet Architecture (cs.NI)
paper · pdf · doi:10.48550/arxiv.1305.4170
openalex publication_date 2013/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a geometric graph, G, the stretch factor between two vertices, u and w, is the ratio between the Euclidean length of the shortest path from u to w in G and the Euclidean distance between u and w. The average stretch factor of G is the average stretch factor taken over all pairs of vertices in G. We show that, for any constant dimension, d, and any set, V, of n points in ℝd, there exists a geometric graph with vertex set V, that has O(n) edges, and that has average stretch factor 1+ on(1). More precisely, the average stretch factor of this graph is 1+O((log n/n)1/(2d+1)). We complement this upper-bound with a lower bound: There exist n-point sets in ℝ2 for which any graph with O(n) edges has average stretch factor 1+Ω(1/√(n)). Bounds of this type are not possible for the more commonly studied worst-case stretch factor. In particular, there exists point sets, V, such that any graph with worst-case stretch factor 1+on(1) has a superlinear number of edges.