I would like to to draw a graph where every edge $e_m$ has a predefined length of $l$. Given that the graph is small and sparse, it should be feasable. However, I did not manage to find an algorithm which does this (or one that is suitable to modify) yet I'm sure that this is a solved problem. Does anyone know of such a layout algorithm and could point me to an implementation or paper?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Unless you provide more constraints, I think it's unlikely to be "solved", since it's easy to find instances for which no solution exists -- e.g., the complete graph on 4 vertices. $\endgroup$– j_random_hackerAug 22, 2017 at 8:22
-
$\begingroup$ @j_random_hacker Yeah, that indeed is a problem. However, as I'm dealing with sparse graphs, this problem is unlikely to happen (and if it does, the constraint can be dropped after n iterations. $\endgroup$– DänuAug 31, 2017 at 7:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
"Planar Embeddings of Graphs with Specified Edge Lengths" by Cabello, Demaine, and Rote (or one of the references they cite) seems to solve your problem.
If you don't care about edges crossing too much, a simple heuristic approach could be gradient descent. Start with a random position and iteratively wiggle the nodes a bit to decrease the sum of differences of the current edge lengths to your desired lengths.
-
$\begingroup$ That's it. I was playing around with a gradient descent approach, however, the edge crossings were the reason I abandoned it. $\endgroup$– DänuAug 31, 2017 at 7:14