# 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!

• For $\lambda =1$ and $m$ Euclidean this is an open problem (by Bruce Kleiner). If $\lambda$ can be arbitrary the question should not be too difficult. – user6976 Apr 16 at 23:10
• Ok, thank you for the reference. What suprises me is that I have only seen mentions of this result (with arbitrary $\lambda$) or explicit proofs in fairly specific cases (compact surfaces for instance). If it holds in greater generality it should certainly appear somewhere in the literature. – Louis Esperet Apr 17 at 7:32
• It's amusing that "weight" is used in a sense that would intuitively be a length... – YCor Apr 17 at 7:39
• Consider the ordinary square lattice on the plane. Assign wait $w$ for every edge $(x,y): w(x,y)=m(x,y)$ where $x,y$ are adjacent vertices. You get a weighted square lattice on the plane. Isn't this embedding a quasi-isometry with $\lambda=2$? – user6976 Apr 17 at 8:53
• Of course number 2 in my previous comment can be arbitrarily large. – user6976 Apr 17 at 10:11

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 ).
• This does not solve the problem: in $R^2$, consider the family of points $1.1\mathbb{Z}\times 1.1\mathbb{Z}$, which is maximal. Then the suggested $G_0$ will not have any $\lambda=1$ approximations to long line segments with slopes like 1/3, violating one of the conditions of the problem. E.g. a segment of the line $y=x/3$ might be approximated by sequences of three horizontal edges and one vertical edge, but that approximation multiplies the length by $4/\sqrt{10} > 1$. – Matt F. Apr 20 at 13:28
• I'm happy with any constant $\lambda$, so I'm accepting this solution. Thank you very much! I completely missed the idea of replacing edge crossings by vertices, that's much simpler than what I had in mind. – Louis Esperet Apr 20 at 19:56