Embedding Graph in Euclidean Space
You may be able to adapt the force-based graph drawing algorithm for your needs.
This algorithm attempts to find a good layout for an undirected graph G(V,E)
by treating each vertex in V
as a Cartesian point and each edge in E
as a linear spring. Additionally, a pair-wise repulsive force (i.e. Coulomb's law) is calculated between vertices globally - this prevents the clustering of vertices in Cartesian space that are non-adjacent in G(V,E)
.
In your case you could set the equilibrium length of the springs equal to your edge weights - this should give a layout with pair-wise Euclidean vertex distances close to your edge weights.
The algorithm updates an initial distribution (possibly random) in a pseudo-time stepping fashion based on the sum of forces at each vertex. The algorithm terminates when an approximate steady-state is reached. A simplified pseudo-code:
while(not converged)
for i = vertices in V
F(i) = sum of spring + repulsive forces on ith vertex
endfor
Update vertex positions based on force vector F
if (vertex positions not changing much)
converged = true
endif
endwhile
There are a number of optimisations that can be applied to reduce the complexity of the algorithm. For instance, a spatial index (such as a quadtree) can be used to allow for efficient calculation of an approximate repulsive force between "near-by" vertices, rather than the slow global calculation. It's also possible to use multi-level graph agglomeration techniques to improve convergence and optimality.
Finally, note that there are several good libraries for graph drawing that implement optimised versions of this algorithm - you might want to check out Graphviz for instance.