Skip to main content

Focused Week: Geometric Spanners

10/23/2023 - 10/29/2023
Rényi Institute


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.


Csaba D. Toth (California State University Northridge)

Invited Speakers

Sujoy Bhore (IIT Bombay)
Hung Le (University of Massachusetts Amherst)


Imre Bárány
Travis Dillon
Zichao Dong
Attila Jung
Balázs Keszegh
Zuzana Patáková
Dániel Simon
Ji Zheng