Embedding point sets into plane graphs of small dilation
(2007) In International Journal of Computational Geometry and Applications 17(3). p.201230 Abstract
 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... (More)
 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. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/969071
 author
 EbbersBaumann, Annette; Gruene, Ansgar; Klein, Rolf; Karpinski, Marek; Knauer, Christian and Lingas, Andrzej ^{LU}
 organization
 publishing date
 2007
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 geometric network, spanning ratio, plane graph, lower bound, stretch factor, dilation
 in
 International Journal of Computational Geometry and Applications
 volume
 17
 issue
 3
 pages
 201  230
 publisher
 World Scientific
 external identifiers

 wos:000251155800002
 scopus:34347339313
 ISSN
 02181959
 DOI
 10.1142/S0218195907002318
 project
 VR 20054085
 language
 English
 LU publication?
 yes
 id
 7f6b3f7d3a4043349540dd3c476f1c48 (old id 969071)
 date added to LUP
 20080129 13:10:54
 date last changed
 20170101 06:37:59
@article{7f6b3f7d3a4043349540dd3c476f1c48, abstract = {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.}, author = {EbbersBaumann, Annette and Gruene, Ansgar and Klein, Rolf and Karpinski, Marek and Knauer, Christian and Lingas, Andrzej}, issn = {02181959}, keyword = {geometric network,spanning ratio,plane graph,lower bound,stretch factor,dilation}, language = {eng}, number = {3}, pages = {201230}, publisher = {World Scientific}, series = {International Journal of Computational Geometry and Applications}, title = {Embedding point sets into plane graphs of small dilation}, url = {http://dx.doi.org/10.1142/S0218195907002318}, volume = {17}, year = {2007}, }