# ## Mohammad Farshi: A Quick Overview of Geometric Spanner Networks

• 2022-11-30
• Guest Professor
• Doctoral School

Mohammad Farshi, Guest Professor at TU Wien Informatics, discusses Euclidean graphs, t-spanners, and their applications.

## A Quick Overview of Geometric Spanner Networks

A geometric network (Euclidean graph) is an edge-weighted graph such that its vertices are points in Euclidean space, and the weight of each edge is the Euclidean distance between its endpoints. A t-spanner of a graph (t ≥ 1) is a subgraph of the graph that preserves the distances between all pairs of points within the multiplication factor t. More precisely, a subgraph G′(V, E′) of G(V, E) is a t-spanner of G, if for any pair of vertices, the distance between them in G′ is at most t times the distance between the two vertices in G. A t-spanner of a set of points is known as a t-spanner of the complete graph on the set of points. This talk aims to give some overview of geometric spanner networks. It will start with an introduction to different well-known algorithms to construct sparse spanners on a given point set, then continue with some quick and rough applications of spanners. In the final part of the talk, some of the current/open research problems will be discussed.