What's the best way to position interconnected nodes in a 2d graph?

Question

I have a list (graph?) of nodes, and each node is connected to other nodes in the list one or more times. I want to take these nodes and lay them out in a nice 2d diagram with lines connecting them together in an optimal way. What's the best algorithm for doing this so that they're spaced evenly apart and the lines connecting them are as untangled as possible?

Answer 1

Use GraphViz.

If you want to learn more about the algorithms used, check out their Theory section.

Here's an example from their Gallery:

Answer 2

I think you'll find that it depends on the data your trying to represent as a graph. There isn't one that fits all.

See: http://networkx.lanl.gov/reference/drawing.html - for some example layouts.

Answer 3

Someone implemented a force-directed graph in JavaScript and gave me permission to do what I want with it: http://www.reddit.com/r/programming/comments/bqr7v/force_directed_graph_layout_in_javascript/c0o4ka5?context=3