PhD Defense Dániel Oláh
On July 9th 2021, Dániel Oláh will defend his PhD thesis titled 'Reliable Geometric Spanners'.
Dániel's promotors are Kevin Buchin (TU/e) and Julia Komjathy (TU/e).
The defense can be followed online starting at 4PM.
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 thesis we 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, spanning ratio) of the network. Since the spanning ratio of the complete graph is always one, 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. Naturally, more edges are needed for spanners that can resist to failures. We give several constructions of spanners that can survive massive failures, while having only a few edges.
You can read the thesis here.