Approach 1
A pretty nice class of algorithms for laying out graphs are simulation-based algorithms. In those algorithms, you model your graph as if it was a physical object with physical properties.
In this case imagine the nodes of the graph are balls that repel each other, while the edges are springs or rubbers that keep the graph together. The repelling force is stronger the closer the nodes are to each other e.g. inverse square of their distance, and the tension force of each spring is proportional to its length. The repelling force will cause the nodes to get as far as possible from the other nodes and the graph will untie. Of course, you'll have to experiment with coefficients a little to get the best results (but I guarantee - it is a lot of fun).
The main pros of this approach are:
- easy to code - nested loops calculating force between every node-node pair and updating node position
- works for all kinds of graphs either planar or nonplanar
- lots of fun to experiment
- if you make it interactive, e.g. allow user to move nodes with a mouse - it attracts people and everyone wants to "play with the graph"
The downsides of this approach are:
- it can get stuck in a local energy minimum (shaking or helping manually helps)
- it is not extremely fast (but can make a nice animation)
A similar method can be used to layout/untie knots.
Sample code
<html>
<head>
</head>
<body>
<canvas id="canvas" width="800" height="600" style="border:1px solid black"/>
<script>
window.requestAnimFrame = (function(callback) {
return window.requestAnimationFrame || window.webkitRequestAnimationFrame ||
window.mozRequestAnimationFrame || window.oRequestAnimationFrame || window.msRequestAnimationFrame ||
function(callback) {
window.setTimeout(callback, 1000 / 120);
};
})();
var width = 800;
var height = 600;
function addEdge(nodeA, nodeB) {
if (nodeA.edges.indexOf(nodeB) == -1) {
nodeA.edges[nodeA.edges.length] = nodeB;
nodeB.edges[nodeB.edges.length] = nodeA;
}
}
function createGraph(count) {
var graph = new Array();
for (var i = 0; i < count; i++) {
var node = new Object();
node.x = Math.floor((Math.random() * width));
node.y = Math.floor((Math.random() * height));
node.edges = new Array();
graph[i] = node;
if (i > 0)
addEdge(graph[i], graph[i - 1]);
}
for (var i = 0; i < count / 2; i++) {
var a = Math.floor((Math.random() * count));
var b = Math.floor((Math.random() * count));
addEdge(graph[a], graph[b]);
}
return graph;
}
function drawEdges(ctx, node) {
for (var i = 0; i < node.edges.length; i++) {
var otherNode = node.edges[i];
ctx.beginPath();
ctx.moveTo(node.x, node.y);
ctx.lineTo(otherNode.x, otherNode.y);
ctx.stroke();
}
}
function drawNode(ctx, node) {
ctx.beginPath();
ctx.arc(node.x, node.y, 30, 0, 2 * Math.PI, false);
ctx.fillStyle = 'green';
ctx.fill();
ctx.lineWidth = 5;
ctx.strokeStyle = '#003300';
ctx.stroke();
}
function drawGraph(ctx, graph) {
ctx.fillStyle = 'white';
ctx.fillRect(0, 0, width, height);
for (var i = 0; i < graph.length; i++)
drawEdges(ctx, graph[i]);
for (var i = 0; i < graph.length; i++)
drawNode(ctx, graph[i]);
}
function distanceSqr(dx, dy) {
return dx * dx + dy * dy;
}
function force(nodeA, nodeB, distanceFn) {
var dx = nodeA.x - nodeB.x;
var dy = nodeA.y - nodeB.y;
var angle = Math.atan2(dy, dx);
var ds = distanceFn(distanceSqr(dx, dy));
return { x: Math.cos(angle) * ds, y: Math.sin(angle) * ds };
}
function repelForce(distanceSqr) {
return 5000.0 / distanceSqr;
}
function attractForce(distanceSqr) {
return -distanceSqr / 20000.0;
}
function gravityForce(distanceSqr) {
return -Math.sqrt(distanceSqr) / 1000.0;
}
function calculateForces(graph) {
var forces = new Array();
for (var i = 0; i < graph.length; i++) {
forces[i] = { x: 0.0, y: 0.0 };
// repelling between nodes:
for (var j = 0; j < graph.length; j++) {
if (i == j)
continue;
var f = force(graph[i], graph[j], repelForce);
forces[i].x += f.x;
forces[i].y += f.y;
}
// attraction between connected nodes:
for (var j = 0; j < graph[i].edges.length; j++) {
var f = force(graph[i], graph[i].edges[j], attractForce);
forces[i].x += f.x;
forces[i].y += f.y;
}
// gravity:
var center = { x: 400, y: 300 };
var f = force(graph[i], center, gravityForce);
forces[i].x += f.x;
forces[i].y += f.y;
}
return forces;
}
function updateNodePositions(graph) {
var forces = calculateForces(graph);
for (var i = 0; i < graph.length; i++) {
graph[i].x += forces[i].x;
graph[i].y += forces[i].y;
}
}
function animate(graph) {
var ctx = document.getElementById("canvas").getContext("2d");
for (var i = 0; i < 20; i++)
updateNodePositions(graph);
drawGraph(ctx, graph);
requestAnimFrame(function() { animate(graph); });
}
animate(createGraph(8));
</script>
</body>
</html>
You can see how this code works here. Refresh the page to get different graphs.
Of course, sometimes it doesn't find the global minimum and there are more crossing edges than it is possible - so if the results don't satisfy you, you can add random shaking.
Approach 2
This problem is similar to routing problem in design of PCBs. If you're not satisfied with the simple and easy solution provided by Approach 1, you can improve the solution by using autorouting methods. E.g. you can put your nodes on a grid and then use A* algorithm to find the shortest paths connecting them.
- Use Approach 1 to find a suboptimal initial solution (optional).
- Remove all edges. Place the nodes on a grid (round up their coordinates). The grid must have enough resolution so that no two nodes overlap.
- Sort the edges in ascending approximated length (use Euclidean or Manhattan metric).
- For each edge use A* algorithm to find the shortest route to connect the nodes. As a cost function use not only the distance from the source node, but also add enough large penalty for stepping onto any grid points that are already taken by any edge routed previously.
- Mark the grid points on the path found in the previous step as "taken", so all next edges will favour paths not stepping on / intersecting with this path.
The above algorithm is a greedy heuristic and unfortunately it doesn't guarantee the optimal solution, because the result depends on the order of routing the edges. You can further improve the solution by removng a random edge that crosses another edge and reroute it.
Step 1. is optional to make the graph layout more regular and make the average connection distance small, however it should not affect the number of intersections (if the grid has enough resolution).
