Regarding the problem from Hughes, one approach is to place the points on a surface such that the length of the geodesic between two points is the weight of the edge. I've always wanted to do something like this, but I can't get past the most basic questions. For example: if the weights assumed the triangle inequality, can you always find a surface?
The other "hack" type approach to the problem I have seen is to take a singular value decoposition on the distance matrix and project along the two largest eigenvectors. But that doesn't always give good results unless the data is very highly clustered.