Xref: utzoo sci.math:7861 comp.graphics:7481
Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!ames!apple!bbn!bbn.com!ischick
From: ischick@bbn.com (Irvin C. Schick)
Newsgroups: sci.math,comp.graphics
Subject: A graph theory question
Message-ID: <45600@bbn.COM>
Date: 14 Sep 89 17:53:54 GMT
Sender: news@bbn.COM
Organization: Bolt Beranek and Newman Inc., Cambridge MA
Lines: 31

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