Ben Seamone, School of Mathematics and Statistices, Carleton University
Informally, a spanning subgraph H of a graph G is referred to as a span- ner if the distance between two points of G is reasonably well preserved in H . More precisely, H is an (?, ?)-spanner of G if d_H(x, y) ? ?ยท d_G(x, y) +? for every pair of vertices x and y, where d(x, y) is some distance function. As it turns out, it is not difficult to construct such spanners; indeed, every graph G is a spanner of itself! The challenge lies in constructing spanners with few edges or, in the case of weighted graphs, of low total weight. Additionally, it is useful to explore construction methods which guaran- tee additional properties, such as bounded degree and low diameter. This talk will give a brief survey of known results on spanners of geometric graphs where distances are given by Euclidean or unit disk metrics, and on the shortest path metric in general graphs.