Minimal Intersection layout algorithm

Question

I would like to know if is there any example of a Minimal Intersection layout algorithm (not force-based) for graphs, so I could adapt it to d3.js.

Answer 1

Computing the layout of a graph that minimizes edge crossings is NP-hard, so there's no single algorithm; there are different algorithms with different trade-offs. The force-based layout (Fruchterman–Reingold) is one approach, layered (Sugiyama) is another. There are also layouts for specific types of graphs, such as trees (Reingold–Tilford) and small worlds (van Ham–van Wijk). Constrained layout such as Dig-CoLa (Dwyer–Koren) is yet another class of algorithm.

If you want an algorithm that specifically seeks to minimize the number of edge crossings, you could use simulated annealing. While this will eventually find the right answer, it can be quite slow.