Focused Week: Geometric Spanners

This focused week is part of the special semester on Discrete Geometry and Convexity.

For a graph \(G=(V,E)\) with edge weight \(w:E\rightarrow \mathbb{R}^+\), a \(t\)-spanner is a spanning subgraph \(H\) such that for all pair of vertices \(u,v\in V\), we have \(d_H(u,v)\leq t\cdot d_G(u,v)\), where \(d_G(u,v)\) denotes the shortest path distance between vertices \(u\) and \(v\) in \(G\). That is, \(H\) distorts distances in \(G\) by a factor of at most \(t\), which is called the spanning ratio or stretch factor of \(H\). The primary focus of this week lies in the regime \(t=1+\varepsilon\) for arbitrarily small \(\varepsilon>0\). It will explore the asymptotic behavior of graph parameters of geometric \((1+\varepsilon)\)-spanners as \(\varepsilon\) tends to zero.