Advanced

Embedding point sets into plane graphs of small dilation

Ebbers-Baumann, Annette; Gruene, Ansgar; Klein, Rolf; Karpinski, Marek; Knauer, Christian and Lingas, Andrzej LU (2007) In International Journal of Computational Geometry and Applications 17(3). p.201-230
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:
author
organization
publishing date
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
0218-1959
DOI
10.1142/S0218195907002318
project
VR 2005-4085
language
English
LU publication?
yes
id
7f6b3f7d-3a40-4334-9540-dd3c476f1c48 (old id 969071)
date added to LUP
2008-01-29 13:10:54
date last changed
2017-01-01 06:37:59
@article{7f6b3f7d-3a40-4334-9540-dd3c476f1c48,
  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 &gt; 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 &lt;= 1.1247. 2. Each embedding of a closed convex curve has dilation &gt;= 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 &gt;= 2/root 3 approximate to 1.1547.},
  author       = {Ebbers-Baumann, Annette and Gruene, Ansgar and Klein, Rolf and Karpinski, Marek and Knauer, Christian and Lingas, Andrzej},
  issn         = {0218-1959},
  keyword      = {geometric network,spanning ratio,plane graph,lower bound,stretch factor,dilation},
  language     = {eng},
  number       = {3},
  pages        = {201--230},
  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},
}