The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Embedding point sets into plane graphs of small dilation

På svenska

Author

  • A Ebbers-Baumann
  • A Grune
  • M Karpinski
  • R Klein
  • C Knauer
  • Andrzej Lingas

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

Department/s

  • Computer Science

Publishing year

2005

Language

English

Pages

5-16

Publication/Series

Algorithms and Computation / Lecture notes in computer science

Volume

3827

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Keywords

  • geometric network
  • dilation
  • plane graph
  • lower bound
  • stretch factor
  • spanning ratio

Conference name

16th International Symposium, ISAAC 2005

Conference date

2005-12-19 - 2005-12-21

Conference place

Sanya, Hainan, China

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 3-540-30935-7