Sparse geometric graphs with small dilation

Boris Aronov, Mark de Berg, Otfried Cheong +4

Given a set S of n points in R^D, and an integer k such that 0 <= k < n, we show that a geometric graph with vertex set S, at most n - 1 + k edges, maximum degree five, and dilatio…