Graph Distance and Euclidean Distance on the Grid

Given a connected graph G = (V, E),V = Z2, on the lattice points of the plane, let d _G (p, q) and d(p,q) denote the graph distance and the Euclidean distance between p and q respectively. In this note we prove that for every є > 0 there is a graph G = G_є and a constant d = d_є such that $$\left| {{d}_{G}}(p,q)-d(p,q) \right|<\varepsilon d(p,q)$$ for every pair p, q ∈ V with d(p, q) ≥ d. It remains open whether or not there is a graph G and a suitable constant K which satisfies $$\left| {{d}_{G}}(p,q)-d(p,q) \right|<K$$ for all p, q ∈ Z2 .