ischick@bbn.com (Irvin C. Schick) (09/15/89)
Being only a lowly statistician, I do not know whether the following graph theory problem is solvable, and if so, how to obtain the required graph. Any help will be greatly appreciated. Suppose you have a finite number of nodes, and a matrix of "distance" measures between all pairs of nodes. (To make matters simple, start out by assuming that the matrix contains only 0s and 1s, with a 1 denoting that the nodes are linked and a 0 that they are not. Eventually, one could use more sophisticated measures: for example, in a communication network, they could be functions of propagation delay -- not linked would then mean infinite delay.) I would like to know if it is possible to construct a 2-D representation such that the distance between pairs of nodes is somehow related to the values given by the matrix. For instance, in the example above, node pairs that are linked might be exactly one unit length appart. (Nodes that are not linked could be unconstrained.) A simple case would be the following: suppose nodes are located on a unit grid, and each node can only be linked to its immediate neighbors. Then the solution is trivial. Now can we generalize? Please reply by e-mail. If there is any interest, I will gladly summarize and post the replies. Irvin
ischick@bbn.com (Irvin C. Schick) (09/16/89)
In article <45600@bbn.COM> ischick@bbn.com (Irvin C. Schick) I wrote: > >Suppose you have a finite number of nodes, and a matrix of >"distance" measures between all pairs of nodes. >... >I would like to know if it is possible to construct a 2-D >representation such that the distance between pairs of >nodes is somehow related to the values given by the matrix. >... Thanks to all those who have replied. The concensus is that if these are true distances, this problem cannot be solved in the general case (triangle inequality and all that), but approximations can be found by using Multidimensional Scaling, and goodness-of-fit measures for such approximations do exist. As the quotation marks around "distance" and the rather loose term "somehow related to the values given by the matrix" suggest, an approximation was all I need, so my question has been answered. Thanks again. Irvin
carlson@lance.tis.llnl.gov (John Carlson) (09/16/89)
In article <45600@bbn.COM> ischick@bbn.com (Irvin C. Schick) writes: >I would like to know if it is possible to construct a 2-D >representation such that the distance between pairs of >nodes is somehow related to the values given by the matrix. >For instance, in the example above, node pairs that are >linked might be exactly one unit length appart. (Nodes that >are not linked could be unconstrained.) I have been reviewing the literature recently and have two good references: "An Algorithm for Drawing General Undirected Graphs", Tomihisa Kamada & Satoru Kawai, Information Processing Letters 31, pp 7-15, 1989. -- discusses treating a graph as a dynamic system. The nodes are linked with "springs." "Automatic Graph Drawing and Readability Diagrams", Roberto Tamassia, Giuseppe di Battista and Carlo Batini, IEEE Transactions on Systems, Man and Cybernetics, Vol 18 #1, Jan/Feb 1988, p 61-79. -- reviews methods, creates a taxonomy, great reference list.