What are some good algorithms for drawing lines between graph nodes? [closed]

Question

What I'm specifically grappling with is not just the layout of a graph, but when a user selects a graph node and starts to drag it around the screen area, the line has to constantly be redrawn to reflect what it would look like if the user were to release the node. I suppose this is part of the layout algorithm?

Also some applications get a bit fancy and don't simply draw the line in a nice curvy way, but also bend the line around the square shaped node in almost right angles. See attached image and keep in mind that as a node is dragged, the line is drawn as marching ants, and re-arranged nicely, while retaining its curved style.

alt text http://img260.imageshack.us/img260/5458/nodesr.png

Answer 1

If your diagrams are not crazy full you should not need an extra-fancy algorithm for this, but just use some common sense.

1. Cover the surface with a rectangular grid and then find a way to connect to boxes with straight lines along grid lines with a minimum number of angles: if the boxes are not on the same grid lines and you don't care where you connect you need one angle if there is no other node in between. If there are e.g. nodes in the way you need at least one more angle.

2. As a second step for fuller diagrams add code that not only optimizes for minimal number of edges but also for minimal length of the lines. If your diagrams are not crazy full this should be hardly noticeable in terms of application response.

3. For extra eye candy round the angles taking into account the lengths of both legs and checking for intersections with other objects on the surface. I would use 90°-pies of circles and adjust the radius of the circles (apparently not what was done above) -- for longer legs the radius should be bigger. Maybe the toolkit you are using can help you here.