David Eppstein - Publications

Beta-skeletons are geometric graphs used among other purposes for empirical network analysis and minimum weight triangulation. A fractal construction shows that, for any beta>0, the beta-skeleton of a point set can have arbitrarily large dilation: Omega(n^c), where c is a constant depending on beta and going to zero in the limit as beta goes to zero. In particular this applies to the Gabriel graph. We also show upper bounds on dilation of the same form.