Spanners 🗓 🗺
SPEAKER: Prosenjit Bose
Prosenjit Bose is a Full Professor at the School of Computer Science in
Carleton University. He is also the Associate Dean of Research and
Graduate Studies for the Faculty of Science.
His homepage is here: http://jitbose.ca/
His CV can be found here: http://www.jitbose.ca/publications/resume.pdf
WHEN
Lecture 1: Wed 12 Apr, 11:30-12:30
Lecture 2: Thu 13 Apr, 11:30-12:30
Lecture 3: Wed 19 Apr, 11:30-12:30
Lecture 4: Thu 20 Apr, 11:30-12:30
WHERE
Sala Riunioni, Primo Piano, Sezione di Informatica e Automazione, Via
della Vasca Navale 79/81.
ABSTRACT
Given a weighted graph G=(V,E) and a real number t≥1, a t-spanner of G is a spanning subgraph G’ with the property that for every edge xy in G, there exists a path between x and y in G’ whose weight is no more than t times the weight of the edge xy. The smallest t for which G’ is a t-spanner of G is called the spanning ratio of the graph G’.
Spanners have been studied in many different settings. The various settings depend on the type of underlying graph G, on the way weights are assigned to edges in G, on the specific value of the spanning ratio t, and on the function used to measure the weight of a shortest path. We concentrate on the setting where the underlying graph is geometric. In this context, a geometric graph is a weighted graph whose vertex set is a set of points in R^2 and whose edge set consists of line segments joining two vertices. The edges are weighted by the Euclidean distance between their endpoints. Given a geometric graph G=(V,E), a t-spanner of G is a spanning subgraph G’ with the property that for every edge xy of G, there is a path from x to y in G’ such that the sum of the weights of the edges in this path is no more than t times d(x,y), where d(x,y) denotes the Euclidean distance between x and y. In the literature, the main focus has been on the case where the underlying graph is the complete geometric graph. We review this case as well as other variants.
There is a vast literature on different methods for constructing t-spanners with various properties in this geometric setting. Aside from trying to build a spanner that has small spanning ratio, additional properties of the spanners are desirable. Typical goals in this area include the construction of t-spanners that also have few edges, bounded
degree, fault tolerance, and low weight, to name a few. Notice that some of these properties actually oppose each other. For example, a graph
with few edges or bounded degree cannot have a high fault-tolerance. Therefore, one needs to balance the various properties.
Our goal is to review results related to the following problem: Given a finite set P of points in R^2, construct a plane t-spanner of the complete geometric graph with vertex set P, for some constant t≥1. We look at different techniques to build plane spanners with various properties such as bounded degree. The link to triangulations come from
the fact that every known method for building such plane t-spanners starts with a variant of the Delaunay triangulation. We also explore the setting where the underlying graph is not the complete graph but some other type of graph such as the unit-disk graph or the visibility graph of a set of line segments. We also explore routing on such graphs. Throughout the lectures, we mention open problems in the area.
