Robust Spanner Networks in the Face of Uncertainty

The quality of geometric networks like road networks is often measured based on distances: a good network should provide relatively short routes between the nodes of the network. In this project we will study the robustness of an important class of geometric networks, namely geometric spanners. The vertex set of a geometric graph is a set of points in the plane (or some higher-dimensional Euclidean space) and the edges are straight line segments, weighted with the Euclidean distance between their endpoints. For some t>1, such a network is a t-spanner if the length of the shortest path between any two vertices is at most t times their Euclidean distance. The factor t is called the dilation (or stretch factor, or spanning ratio) of the network. Since the complete graph is always a spanner, the challenge is to construct spanners with constant dilation that have as few edges as possible. There are several constructions of linear size spanners, which are optimal.

Robust spanners should have  the  property that  a small  spanning ratio  is maintained in the case of vertex failures. The residual network should contain a huge component such that the relatively short distances are preserved for all pairs within the component. That is, there may be some additional loss, but the size of this loss is strictly bounded by some function of the number of deleted vertices. The aim of our project is to study robust geometric spanners both in deterministic and stochastic settings. The main goal is to give constructions of robust spanners of small size, while also maintaining a constant dilation and a sharp bound on the amount of the loss. Another goal of the project is to extend the results to general metric spaces.