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

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 🙂

Leave a Comment