(Directed) Graph Parameters for Geometric Spanners

• Applicant: Dr. Carolin Rehs
• Subject Area: Theoretical Computer Science
• Term: since 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 550144388

Geometric graphs are of high interest for many applications: Road and train networks, robot motion planning, wireless ad-hoc networks, and many more. To work with and run algorithms on these graphs, it is often useful to approximate the complete graph by smaller versions of the graph, in particular by a graph with fewer edges. However, there are important properties which should not be altered by this. Especially the distance between two points in the graph should not get much larger than their distance in a complete euclidean graph: a graph with this property is called geometric spanner. Formally, let P be a point set in the euclidean plane. A geometric spanner for P is a weighted subgraph G=(P,E,w) of the complete graph on P, where the weight w(e) of an edge e is the euclidean distance between the start and ending point of e. The idea of a geometric spanner is finding an edge set E which is not too big while the path between two points in P does not get too long. This is formalised by the so-called dilation factor t= max{ d((p,p')/|p,p'| with p,p' points in P }, where d(p,p') is the distance between two points in G and |p,p'| is the euclidean distance between p and p'. A geometric spanner with dilation t is also called a t-spanner. In computational geometry, the most frequently considered property of a spanner - next to its dilation - is its size. Commonly, geometric spanners are required to have a linear or near-linear number of edges, or the number of edges is implicitly bounded by other properties such as planarity. Further measures are total weight or maximum vertex degree. In graph theory, an important tool to design efficient algorithms for in general NP-hard problems is to bound the input graphs in certain parameters as tree-width or clique-width. In our research we will consider spanners which are bounded by these parameters, which will allow the application of many graph theoretical results on geometric problems and especially allow efficient algorithms for many applications.

• DFG Programme: Research Grants
• Co-Investigator: Professor Dr. Kevin Buchin