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!

  • $\begingroup$ 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. $\endgroup$
    – user6976
    Apr 16, 2020 at 23:10
  • $\begingroup$ 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. $\endgroup$ Apr 17, 2020 at 7:32
  • $\begingroup$ It's amusing that "weight" is used in a sense that would intuitively be a length... $\endgroup$
    – YCor
    Apr 17, 2020 at 7:39
  • $\begingroup$ 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$? $\endgroup$
    – user6976
    Apr 17, 2020 at 8:53
  • $\begingroup$ Of course number 2 in my previous comment can be arbitrarily large. $\endgroup$
    – user6976
    Apr 17, 2020 at 10:11

2 Answers 2


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 ).

  • $\begingroup$ 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$. $\endgroup$
    – user44143
    Apr 20, 2020 at 13:28
  • $\begingroup$ 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. $\endgroup$ Apr 20, 2020 at 19:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.