BARC talk by Antonia Kalb

Tuesday, September 30, 2025, Antonia Kalb, PhD student at TU Dortmund University, Germany, will give a talk on "Oriented Spanners".

Abstract:
Geometric graphs naturally model numerous real-life networks, including road and train networks. In the design of these networks, several criteria can be taken into account. In many applications ensuring a fast connection between every pair of points is essential. While the complete graph offers an optimal solution with direct connections between all points, its quadratic size is often impractical. Thus, the focus shifts to approximating the complete graph with fewer edges while considering additional properties such as directions.
While geometric spanners have been researched for decades, directed versions have only been considered more recently. This is surprising since, in many applications, edges may be directed or even oriented if two-way connections are not permitted. Oriented spanners were first introduced in ESA'23. Since then, a variety of problems have been considered in the setting of oriented spanners.
This talk gives an overview of the results on oriented spanners gained in the last three years. We will take a closer look on the first algorithm that computes a sparse oriented spanner whose oriented dilation is bounded by a constant (SoCG'25).

Bio:
Antonia Kalb is a PhD student and research associate in computational geometry at TU Dortmund University, Germany, where she works with Kevin Buchin at the Algorithm Engineering Chair. As a teaching assistant, she coordinates tutorials for courses such as Data Structures and Algorithms. She completed both her Bachelor's and Master's degrees at TU Dortmund University. Antonia's research interests include geometric graphs and algorithms, with a primary focus on constructing geometric spanners under various restrictions and requirements.
Antonia is visiting BARC from mid-September to mid-November 2025 on a fellowship from the German Academic Exchange Service (DAAD).

Host:
Sampson Wong