BARC Talk by Katharina Klost: Shortest Path in general disk graphs... & Sarita de Berg: The Complexity of Geodesic Spanners

Katharina Klost: Shortest Path in general disk graphs and an algorithmic framework for SSSP

The unweighted single source shortest path problem is among the fundamental problems in graph theory. We can show that there is an O(n log^2 n) time algorithm for general disk graphs. A disk graph is defined on a set of disks in the plane. There is a vertex for each disk and two disks are connected by an edge if and only if they intersect. Then we generalize the ideas from this algorithm to describe an algorithmic framework that yields single source shortest paths algorithms for graph classes that allow efficient algorithms for certain operations.

Sarita de Berg: The Complexity of Geodesic Spanners

A \emph{geometric $t$-spanner} for a set $S$ of $n$ point sites is an edge-weighted graph for which the (weighted) distance between any two sites $p,q \in S$ is at most $t$ times the original distance between $p$ and~$q$. We study geometric $t$-spanners for point sets in a constrained two-dimensional environment $P$.In such cases, the edges of the spanner may have non-constant complexity.
Hence, we introduce a novel spanner property: the spanner \emph{complexity}, that is, the total complexity of all edges in the spanner. Let $S$ be a set of $n$ point sites in a simple polygon $P$ with $m$ vertices. In the talk we will see  an algorithm to construct, for any constant $\varepsilon>0$ and fixed integer $k \geq 1$, a $(2k + \varepsilon)$-spanner with complexity $O(mn^{1/k} + n\log^2 n)$. Then, we consider sites in a polygonal domain $P$ with holes, and discuss how to overcome the additional difficulties that arise.