  Embedding graphs in a geographical or latent space, i.e.\ inferring locations
for vertices in Euclidean space or on a smooth manifold or submanifold, is a
common task in network analysis, statistical inference, and graph
visualization. We consider the classic model of random geometric graphs where
$n$ points are scattered uniformly in a square of area $n$, and two points have
an edge between them if and only if their Euclidean distance is less than $r$.
The reconstruction problem then consists of inferring the vertex positions, up
to the symmetries of the square, given only the adjacency matrix of the
resulting graph. We give an algorithm that, if $r=n^\alpha$ for any $\alpha >
0$, with high probability reconstructs the vertex positions with a maximum
error of $O(n^\beta)$ where $\beta=1/2-(4/3)\alpha$, until $\alpha \ge 3/8$
where $\beta=0$ and the error becomes $O(\sqrt{\log n})$. This improves over
earlier results, which were unable to reconstruct with error less than $r$. Our
method estimates Euclidean distances using a hybrid of graph distances and
short-range estimates based on the number of common neighbors. We extend our
results to the surface of the sphere in $\R^3$ and to hypercubes in any
constant fixed dimension. Additionally we examine the extent to which
reconstruction is still possible when the original adjacency lists have had a
subset of the edges independently deleted at random.
