EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, Marek Karpiński, Christian Knauer, Andrzej Lingas · International Journal of Computational Geometry & Applications · 2007
Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound > 1. In this paper we provide the first upper and lower bounds for the embedding problem. 1. Each finite point set can be embedded into the vertex set of a finite triangulation of dilation ≤ 1.1247. 2. Each embedding of a closed convex curve has dilation ≥ 1.00157. 3. Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation [Formula: see text].