33 citations · 73 across the 19 of their papers we have counts for
Showing 2007Show all
2 papers · 1 filter
cs.CG2007★ 1 cited
Computing a Minimum-Dilation Spanning Tree is NP-hard
Otfried Cheong, Herman Haverkort, Mira Lee
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 fac…
cs.CG2007★ 2 cited
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…