We are given a directed graph with weights on the edges; i.e., there are (directed) edges (i,j) (and potentially (j,i)) between some pairs of nodes i and j, having ``weights'' d(i,j). Our goal is to draw the nodes as points in the plane (or in 3-space) in such a way that proximity is (at least approximately) preserved: i.e., if d(i,j) is ``small'' then nodes i and j are ``close'', while if d(i,j) is ``large'', then nodes i and j are ``far'' apart (say, roughly in proportion to the weight d(i,j)). In this way, we would like to be able to visualize a weighted directed graph, so that the user can assess proximity relationships graphically.
What can be said theoretically?
What can be done practically? How efficient of a heuristic can you suggest? Can you guarantee any quality bounds?
Questions: