I'm looking for the name of a graph construction.
My initial problem is to construct a graph from a set of points $(s_i)_i=((x_i,y_i))_i$ which are going to be my vertices. I can thus define the usual Euclidian distance $d(s,t)$ between my vertices.
Now I want to add edges to my graph $G=(V,E)$, so it looks like the road map.
I could join each vertex $s_i$ to its $k$ nearest neighbours, but then I won't get the type of connection I want.
My idea is to connect two nodes $s,t$ if there is no other vertex in the graph near the geodesic between $s$ and $t$. The condition looks like
$$(s,t) \in E \Longleftrightarrow \nexists u \in V \setminus \{s,t\}, d(s,u) + d(u,t) \leq (1+\rho) d(s,t)$$
(here $\rho$ is some positive parameter controlling how close to the geodesic a node can be).
example
If the points are $(0,0),(-2,0), (-1,0), (4,0), (0.01,0.5)$ and $(0,1)$ then
if $\rho = 0$
the neighbours of $s=(0,0)$ will be $\{(-1,0),(4,0), (0.01,0.5), (0,1) \}$ (but not $t=(-2,0) $ because for $u=(-1,0)$ we have $d(s,u) + d(u,t) = (1+\rho) d(s,t)$
if $\rho = 0.1$ the neighbours of $s=(0,0)$ will be $\{(-1,0),(4,0), (0.01,0.5)\} $ (but not $t=(0,1) $ because for $u=(0.01,0.5)$ we have $d(s,u) + d(u,t) \leq (1+\rho) d(s,t)$.
I would like to know if such a construction has a name, since I could not find one.
Sorry if the question is a bit fuzzy.