  In a random linear graph, vertices are points on a line, and pairs of
vertices are connected, independently, with a link probability that decreases
with distance. We study the problem of reconstructing the linear embedding from
the graph, by recovering the natural order in which the vertices are placed. We
propose an approach based on the spectrum of the graph, using recent results on
random matrices. We demonstrate our method on a particular type of random
linear graph. We recover the order and give tight bounds on the number of
misplaced vertices, and on the amount of drift from their natural positions.
