Quasi-isometric embedding of graphs in non-compact riemannian surfaces 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!
 A: 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 ).
A: Can you choose G so that its face-boundaries have uniformly bounded lengths? (Equivalently, so that every face of G is bounded by a triangle).
Perhaps you can fiddle around a little to get rid of intersections too close to the x_i, so that your edges have lengths bounded below. Thus, for a different λ, you could let all edges of G have length 1.
