2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)

A geometric graph G is a graph whose vertices are points in the plane and whose edges are line segments weighted by the Euclidean distance between their endpoints. In this setting, a t-spanner of G is a connected spanning subgraph G' with the property that for every pair of vertices x, y, the s...

Ausführliche Beschreibung

Gespeichert in:
1. Verfasser:
IEEE Staff (MitwirkendeR)
Körperschaft:
International Symposium on Voronoi Diagrams in Science and Engineering
Format:
Elektronisch E-Book
Sprache:
Englisch
Veröffentlicht:
[Place of publication not identified] IEEE 2012
Zusammenfassung:
A geometric graph G is a graph whose vertices are points in the plane and whose edges are line segments weighted by the Euclidean distance between their endpoints. In this setting, a t-spanner of G is a connected spanning subgraph G' with the property that for every pair of vertices x, y, the shortest path from x to y in G' has weight at most L ≥ 1 times the shortest path from x to y in G. The parameter t is commonly referred to as the spanning ratio or the stretch factor. Among the many beautiful properties that Delaunay graphs possess, a constant spanning ratio is one of them. We provide a comprehensive overview of various results concerning the spanning ratio among other properties of different types of Delaunay graphs and their subgraphs.
Umfang:
1 online resource (xii, 150 pages) : illustrations
Anmerkungen:
Bibliographic Level Mode of Issuance: Monograph
Anmerkungen:
English
Schlagworte:
Engineering mathematics > Congresses.
Bezugswerke: