TU Wien Informatics

20 Years

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.

Mohammad Farshi: A Quick Overview of Geometric Spanner Networks
Picture: stock.adobe.com

A Quick Overview of Geometric Spanner Networks

By Mohammad Farshi

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.

About Mohammad Farshi

Mohammad Farshi holds a BSc in Computer Science from Yazd University, Iran (1992-1996) and an MSc in Pure Mathematics from Shiraz University, Iran (1996-1999). He gained his Ph.D. in Computer Science at TU Eindhoven, The Netherlands (2004-2008). From 2007 to 2009, Mohammad Farshi was a Postdoc at Carleton University, Canada. Before that, he was a Lecturer at Yazd University, Iran (1999-2004). From 2009 to 2020, Mohammad Farshi was Assistant Professor at Yazd University, Iran, where, in 2020, he was appointed Associate Professor. He has supervised five Ph.D. students and 27 Master’s students.

For Students

The lecture series of research talks by the guest professors of the TU Wien Informatics Doctoral School can also be credited as an elective course for students of master programs of computer science: 195.072 Current Trends in Computer Science.

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.