What is known about plane graphs (i.e., graphs with a specified imbedding in the plane) with the following properties? (a) The graph is connected. (b) The number of vertices within Euclidean distance R of the origin grows like a constant times R^2. (c) As the Euclidean distance between vertices goes to infinity, the ratio between the Euclidean distance and the graph-theoretic ("Kevin Bacon") distance goes to 1. Property (c) is the important one. Properties (a) and (b) are included only to rule out trivial examples that aren't in keeping with the underlying spirit of the question (which is to find a discrete plane graph from which the Euclidean metric of R^2 can be reconstructed, at least in the large --- what one might call an "asymptotically Euclidean" plane graph). My guess is that there are random constructions that yield such a graph with probability 1, but that deterministic constructions that look like they do the job are harder to come by, and that deterministic constructions that can be _proved_ to do the job are harder still to come by. I suspect that one can find such a graph that also satisfies the following two conditions: (d) There is a universal bound on the Euclidean distance between two vertices that are connected to each other. (e) The vertices form an infinite square lattice. A more difficult problem would be to find an infinite graph of this kind that admits a finite-state local construction procedure. Let me not be too precise about what I mean by this, since there are several possible definitions, and I'm not 100% sure that they're equivalent. But the idea, on an informal level, is to build up an asymptotically Euclidean network of "sessile grogs", starting from just one sessile grog, where a sessile grog (1) lives in the plane, (2) can't move, (3) has limited computational power, (4) has limited-range telepathy, and (5) can create other sessile grogs nearby, each of which also satisfies (1)-(5). If one could do this, one might liberate the grogs from the plane and give a completely non-geometric version of grog-life in which abstract grogs, starting from one Ur-Grog, create a network whose large-scale metric properties are just like those of R^2. (By the way, "Sessile Grogs" are inhabitants of Larry Niven's fictional "Known Space" universe.) Jim Propp