Constructing and Routing on Geometric Spanners

Abstract

A geometric graph $G=(V,E)$ is a graph whose vertex set $V$ is a set of points in the plane and whose edge set $E$ is a set of segments joining vertices. Typically, the edges are weighted with the Euclidean distance between their endpoints and we refer to such graphs as Euclidean geometric graphs. A spanning subgraph $H$ of a Euclidean geometric graph $G$ is a $t$-spanner of $G$ provided that for every edge $xy\in G$, the shortest path between $x$ and $y$ in $H$ has weight that is no more than $t$ times the weight of the edge $xy$. The smallest constant $t$ for which $H$ is a $t$-spanner of $G$ is its spanning ratio.

An online routing algorithm $𝒜$ is an algorithm that finds a short path in a graph without having full knowledge of the graph. The routing ratio of $𝒜$ is analogous to the spanning ratio except that the ratio is with respect to the weight of the path followed by the routing algorithm as opposed to the shortest path. Thus, the routing ratio, by definition, is an upper bound on the spanning ratio.

In this talk, we will review results and present open problems on different variants of the problem of constructing and routing on geometric $t$-spanners.