
Evènement pour le groupe Séminaire du LaBRI
Date  20101021 14:0015:00 
Titre  Sém LaBRI. On Plane Geometric Spanners 
Résumé  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 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 $t geq 1$ times the shortest path
from $x$ to $y$ in $G$. The parameter $t$ is commonly referred to
as the {em spanning ratio}, the {em dilation} or the {em
stretch factor}. In addition to having bounded spanning ratio, it
is desireable to build $t$spanners that possess other
properties, such as bounded degree, low weight, or
faulttolerance to name a few. In this talk, we are particularly
interested in planarity. We review various results in the
literature on how to build spanners that are planar. 
Lieu  Amphi LaBRI 
Orateur  Prosenjit Bose 
Url  Carleton University, Canada 
Aucun document lié à cet événement. RetourRetour à l'index
 