Initially, we proceeded to simplify the problem to see what could be done theoretically. For example, any weighted tree can be perfectly embedded in the line. Certain simple graphs cannot be embedded at all - consider a triangle with two short edges and one long edge. Steve claimed that the problem of testing whether a graph can be realized exactly is known to be hard, and asserted that this is proven in James B. Saxe, ``Embeddability of Weighted Graphs in k-Space is Strongly NP-Hard'', Proc. Allerton Conference on Computers, Controls, and Communications, v. 19, 480-489, Urbana, IL, 1979
However, the problem called more for a practical heuristic than a theoretical result. The first class of algorithms we considered were based on spring-embedding heuristics, which model the graph as a system of strings, with the forces on each edge defined by its weight. Solving this system numerically moves the vertices around so as to adjust to the forces.
A different approach seemed to me to be very interesting. Heuristically find a partition of the graph - a way to cut it into two components of roughly equal size using while cutting few edges. Recursively find embeddings of the two components. Finally, stitch the two components together by finding a translation/rotation of the first component which optimizes the lengths of the edges between the components.