If we take the integer lattice in $\mathbb{R}^2$ and make edges from $(m,n)$ to $(m+1,n)$ and $(m,n+1)$, you get your typical city block street layout, and if we put the shortest path metric on the graph we created (where distance is fewest number of hops from one intersection to another), then we get a metric equal to the taxicab metric on $\mathbb{R}^2$.
Now the taxicab metric is off from the Euclidean metric by at most a factor of $\sqrt{2}$. How well can we embed a graph into $\mathbb{R}^2$ so that its shortest path metric approximates the Euclidean metric really well, and more or less covers $\mathbb{R}^2$ reasonably well. Clearly, you'll not be able to approximate small distances well, but maybe you can approximate long distances pretty well?
Here is a precise form of my question: is there a way to embed the vertices of an infinite graph $G = (V,E)$ with shortest path metric into $\mathbb{R}^2$ with function $f:V\rightarrow\mathbb{R}^2$ such that the covering radius of $f(V)$ is at most, say 2, and asymptotically there is no distortion in the metric. By asymptotically no distortion, I mean that as long as we pick two points in the image $f(V)$ far enough away in $\mathbb{R}^2$, then ratio of Euclidean and graph distance is as close as we want to 1. To be precise, that is
$\displaystyle \lim_{R\rightarrow\infty} \sup_{|f(x)-f(y)|>R}\left|\frac{|f(x)-f(y)|}{d(x,y)} - 1\right|$ = 0,
Where $d(x,y)$ is smallest number of hops from $x$ to $y$. If the limit is not $0$, how well can we do? We see the city-block arrangement above gets the limit down to $\sqrt{2} - 1$, so is it possible to do better?
Also if you know any related sources or similar problems I'd love to know. Thanks in advance.
EDIT
Also require that the image $f(V)$ is a planar graph (with straight lines drawn from $f(v)$ to $f(w)$ when $(v,w)\in E$).
That's much too optimistic. A basic problem is that the cycle $C_4$ does not embed well into any Euclidean space. The generalized parallelogram law is to blame: the sum of squares of diagonals cannot exceed the sum of squares of the sides. For $C_4$ the diagonals are of length $2$ each, while the sides are $1$ unit each. Since $$2^2+2^2>1^2+1^2+1^2+1^2\tag1$$ distortion cannot be brought arbitrarily close to $0$. One of two sides of (1) will have to change at least by the factor of $2^{1/2}$ in the embedding, which means at least one of the distances will be distorted at least by $2^{1/4}$ (either way).
The square grid contains arbitrarily large copies of $C_4$, such as $(0,0)$, $(0,R)$, $(R,R)$, $(R,0)$. So much for having distortion near $1$ (and I haven't even used the covering radius). The obvious square embedding is the best you can do, although you can improve on $\sqrt{2}-1$ by magnifying it a little: let the sidelength be $2^{1/4}$.
It gets worse for more general graphs. In a comment, GCD pointed out the binary trees, for which the volume growth is an issue: they have so many vertices in a ball of radius $R$ that you can't put them in a Euclidean space simply for lack of room.
There is another, subtler obstacle. One can put $C_4$ into $C_4$ iteratively. The straightforward way to do this is to replace each edge of $C_4$ with four edges forming $C_4$. This gives the Newman-Rabinovich diamond graphs, which have the same volume growth problem as the trees. Another way is to replace only a part of each edge with a copy of $C_4$. This gives a prettier picture: Laakso graphs.
There are no obvious volume growth issues here: the number of vertices in a ball of radius $R$ has polynomial growth with $R$. Yet, any embedding of $k$th generation Laakso graph into a uniformly convex Banach space must have distortion growing to infinity with $k$. Restriction to large distances does not help since the iteration can proceed outward, by adding larger and larger copies of the graph (instead of smaller and smaller details).
Recommended reading: Geometry of cuts and metrics by Deza and Laurent. (Available from Deza's webpage).