Given a complete riemannian surface $(S,m)$, where $S$ is homeomorphic to $\mathbb{R}^2$, I would like to find a weighted graph $G$ (which means a graph with real non-negative weights on the edges), embedded in $S$, and such that the (weighted) shortest path metric in $G$ is quasi-isometric to $m$ (this means that there are constants $\lambda,\epsilon,C$ such that for any vertices $x,y$ in $G$, $\tfrac1\lambda d\_G(x,y)-\epsilon \le d\_m(f(x),f(y)) \le \lambda d\_G(x,y)+\epsilon$, where $f$ denotes the embedding of $G$ in $S$, and every point of $S$ is at distance at most $C$ from some vertex of $G$).


Note that in particular $G$ will be planar. I need that in addition, $G$ is countable and locally finite (meaning that any bounded region of $S$ contains only a finite number of vertices of $G$).


I have seen such statements proved for compact surfaces (in this case $G$ can be taken to be finite), or non-compact surfaces with some uniform bounds on the curvature or strong convexity radius (in both cases the vertex set is just an $\epsilon$-net on the surface, for a sufficiently small $\epsilon>0$), but I suspect the result holds in much greater generality.


I am not an expert in riemannian geometry and I lack some background in the area. Have you seen such a statement proved in a clean way in an article or a textbook? Thank you in advance!



Quasi-isometric embedding of graphs in non-compact riemannian surfaces
This follows from the usual "economic covering" method: By Zorn (but alternatively, you can easily do it with your bare hands without using the choice axiom), $S$ admits a maximal family $(x\_i)$ of 1-separated points (meaning that the distance between $x\_i$ and $x\_j$ is at least 1 for $i\neq j$). Then, the balls $B\_i$ of center $x\_i$ and radius $2$ cover $S$; but consider rather the covering by the larger balls $B'\_i$ of center $x\_i$ and radius $5/2$. Clearly, every geodesic segment in $S$ of length $\le 1$ lies in a ball $B'\_i$.
Let $G\_0$ be the $1$-skeleton of this covering $(B'\_i)$: its vertices are the $x\_i$'s; its edges are the pairs $(x\_i,x\_j)$ s.t. $B'\_i$ intersects $B'\_j$. Put the weight $1$ on each edge. By choosing a shortest geodesic between $x\_i$ and $x\_j$ for each edge, you get a map $f:G\_0\to S$ which is clearly a quasi-isometry (indeed, given any shortest geodesic $\gamma$ on $S$ of length $\le n$, cut it into $n$ segments $[y\_k,y\_{k+1}]$ of length $\le 1$; one has a vertex $v\_{i\_k}$
of $G\_0$ at distance $\le 2$ from each point $y\_k$; by the triangle inequality, $B'\_{i\_k}$ and
$B'\_{i\_{k+1}}$ intersect; hence $\gamma$ lies at Hausdorff distance $2$ of a simplicial path in $G\_0$ of length $\le n$). Of course, $f$ is not an embedding in general; however it is locally finite (any compact subset of $S$ meets only finitely many edges); in particular, once you have added the intersections of the edges as new vertices, you get an embedded, locally finite, quasi-isometric graph $G$.


(Of course, the nature of the problem changes if one adds the extra requirement that $\lambda=1$; which I do not ).


