2
$\begingroup$

Is it possible to calculate the x,y position of a node in a complete weighted graph with euklidic metric when i have the weight of every edge in the graph? it would be really usefull for me to plot such a graph... i coulnd find any algorithm which can do this :(

$\endgroup$
  • $\begingroup$ Is the weight of each edge given by the Euclidean distance between the two vertices on that edge? $\endgroup$ – Chris Taylor Jun 15 '11 at 11:17
  • $\begingroup$ yes it is... but i have some graphs were it isnt... i think it woulnd work there right? $\endgroup$ – reox Jun 15 '11 at 11:18
2
$\begingroup$

Let me add detail to user6312's suggestion.

Because a triangle is rigid, you can start by finding three mutually connected nodes in your graph, embedding that in the plane (say, in some standard position: one vertex at the origin, one on the $x$-axis, one in the positive quadrant), and then building upon that triangle. Call the first triangle $(a,b,c)$. The building could be accomplished by selecting another node $p$ connected to $a$, $b$, and $c$, and computing its location from the distances $|ap|$, $|bp|$, $|cp|$. Intersecting the circles for two of those distances yields two possible locations for $p$, and the third distance can serve to disambiguate.

$\endgroup$
1
$\begingroup$

This type of problem has been considered by others, and there are various algorithms available. I imagine that there is also ready-made code available.

The following reference may give you a start. There weights are the Euclidean distances.

You could develop something on your own, based on straightforward analytic geometry. Do like surveyors do, compute the coordinates of a base triangle, preferably a fairly large one. Then the locations of the remaining points can be found by intersecting suitable circles. The algebra is not too bad.

However, there are more efficient ways to proceed, and if your graph is has a fair number of vertices, the naive geometric approach will be excessively slow.

Added: The base triangle should also be fairly round, the smallest angle should not be too small. This will improve the numerical stability of the algorithm.

$\endgroup$
  • $\begingroup$ so if i understand you right, i take just three points out of my list and set for the first a pseduo coordinate e.g. (10,10). then i take another and set it on the same x axis with the distance weight and then the third node on the calculated point between a and b? $\endgroup$ – reox Jun 15 '11 at 21:14
  • $\begingroup$ I would put one point $P$ at $(0,0)$, another point $Q$ at $(d,0)$ where $d$ is the distance between $P$ and $Q$. The third point $R$ is put at the place $(a,b)$ which is at the right distances from $(0,0)$ and $(d,0)$. $\endgroup$ – André Nicolas Jun 15 '11 at 21:26
  • $\begingroup$ @reox (continued) There are two choices for $R$, pick one. After that, the locations of the remaining points can be computed using the base triangle $PQR$. But I still would advise using someone else's work. Professionals write highly optimized code, and take care of subtle side issues. $\endgroup$ – André Nicolas Jun 15 '11 at 21:35
  • $\begingroup$ i wrote some piece of code now, and its working someway :D yes best is to try somebody elses code, but mine is a little bit proove of concept anyway, this should work for me! thank you a lot! $\endgroup$ – reox Jun 22 '11 at 11:53
  • $\begingroup$ @reox: I am happy that you got some possibly useful ideas from the various responses. $\endgroup$ – André Nicolas Jun 22 '11 at 15:03
0
$\begingroup$

Try neato from Graphviz.

$\endgroup$
  • $\begingroup$ mhh is there any cool option? otherwise its not working really good.... $\endgroup$ – reox Jun 15 '11 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.