D3.js force directed graph, reduce edge crossings by making edges repel each other

Question

So i have a page already which draws a force directed graph, like the one shown here.

And that works fine. I'm using the JS from here, with a few tweaks to spread out the nodes slightly nicer.

These are more or less the only differences:

d3.json("force.json", function(json) {   var force = d3.layout.force()       .gravity(0.1)       .charge(-2000)       .linkDistance(1)       .linkStrength(0.1)       .nodes(json.nodes)       .links(json.links)       .size([w, h])       .start(); 

Where reducing the link strength seems to make the links more like springs, so it becomes similar to the Fruchterman & Reingold technique often used. This works reasonably well, but only for fairly small graphs. With larger graphs the number of crossings just goes up - as one would expect, but the solution it lands on is normally far from optimal. I'm not looking for a method to get the optimal solution, I know that's very difficult. I would just like it to have some crude addition that tries to force the lines apart as well as the nodes.

Is there a way to add a repulsion between in links, as well as between the nodes? I'm not familiar with the way D3 force works, and i can't seem to find anything that says this is possible...

Answer 1

Unfortunately, the answer to your question does not exist.

There is no built-in mechanism in D3 that repels edges or minimizes edge crossings. You would think it wouldn't be that hard to implement a charge on an edge, but here we are.

Furthermore, there doesn't seem to be any mechanism anywhere that reduces edge crossings in general. I've looked through dozens of visualization libraries and layout algorithms, and none of them deal with reducing edge crossings on a generic undirected graph.

There are a number of algorithms that work well for planar graphs, or 2-level graphs, or other simplifications. dagre works well in theory for 2-level graphs, although the utter lack of documentation makes it almost impossible to work with.

Part of the reason for this is that laying out graphs is hard. In particular, minimizing edge crossings is NP-hard, so I suspect that most layout designers hit that problem, bang their head against the keyboard a few times, and give up.

If anyone does come up with a good library for this, please publish it for the rest of us :)

Answer 2

Something that might be easier than trying to forcefully repel the edges is to wiggle the nodes around until the amount of crossing lines in the system is lower.

http://en.wikipedia.org/wiki/Simulated_annealing

Start with the nodes with the least amount of connections and wiggle down.

If you try and use the edges as nodes I suspect you're just going to get the same spatial locking problems. The solution is in figuring out where there are edge intersections and if they can be resolved. You might find that resolving many of the edge crossings is not possible

A more lateral approach to the visualization is to animate it such that it only shows a subset of the nodes and connections at a time. Or to make the edges transparent until the user places mouse focus over a node, which point the associated edges become more visible.