Embedding point sets into plane graphs of small dilation

Summary, in English

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 in to 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 >= 2/root 3 approximate to 1.1547.

• Författare: Annette Ebbers-Baumann; Ansgar Gruene; Rolf Klein; Marek Karpinski; Christian Knauer; Andrzej Lingas
• Avdelning/ar: Computer Science
• Publiceringsår: 2007
• Språk: Engelska
• Sidor: 201-230
• Publikation/Tidskrift/Serie: International Journal of Computational Geometry and Applications
• Volym: 17
• Issue: 3
• Länkar: http://dx.doi.org/10.1142/S0218195907002318
• Dokumenttyp: Artikel i tidskrift
• Förlag: World Scientific Publishing
• Ämne: Computer Science
• Nyckelord: geometric network; spanning ratio; plane graph; lower bound; stretch factor; dilation
• Status: Published
• Projekt: VR 2005-4085
• ISBN/ISSN/Övrigt: ISSN: 0218-1959