(Weakly) Self-approaching graphs

VCLA hosted a talk by Mohammad Farshi

DATE:	Monday, November 13, 2017
TIME:	16:30 s.t.
VENUE:	Library, Favoritenstraße 9-11, Stairs 2, Floor 4 (HB 04 08)

ABSTRACT

A geometric graph is called self-approaching if,  for each (ordered) pair of vertices of the graph, there exists a self-approaching (directed) path between them. A path from a vertex $u$ to a vertex $v$ is called self-approaching, if for any point (not just vertex) $x$ on the path, the distance between $x$ and any point that starts at $u$ and moves toward $x$ is decreasing. A path is called increasing-chord, if it is self-approaching from both sides, source to destination and destination to source. A geometric graph is called a self-approaching $t$-spanner, for $t>1$, if for each pair $(u,v)$ of vertices of the graph, there exists a self-approaching path from $u$ to $v$ of length at most $t$ times the Euclidean distance between $u$ and $v$.

In the talk, we first show existence of increasing-chord planar graph for some special cases. Then we make the conditions of self-approaching graph weaker and define weak self-approaching geometric graphs and we show that for every point set $Ssubseteq R ^d$, there is a weakly self-approaching planar geometric graph spanning $S$. Furthermore, we show how to test in polynomial time, whether a given geometric graph is weakly self-approaching. Notably, the corresponding decision problem in the context of self-approaching geometric graphs in $R^d$ with $d geq 3$ is NP-hard.

Then, we propose some algorithms for constructing a weakly self-approaching geometric $t$-spanner for a given point set and a real constant  $t > 1$. Also, we show that for every point set $S$  on the boundary of any  triangle, there exists  an increasing-chord $t$-spanner spanning $S$ and a weakly self-approaching $t$-spanner  spanning $S$, both with $O(kn)$ edges, in which  $k$ depends only on $t$. Biography: Prof. Mohammad Farshi is Assistant Professor in the Computer Science Department of Yazd University in Iran since 2009. He got his PhD degree in 2008 from the algorithms group of TU Eindhoven (Netherlands) focusing on geometric networks and he was a postdoctoral fellow at Carleton University, Ottawa (Canada) from 2007—2009.