I’m very interested in graphviz’s minimum crossover algorithm, and I tried the algorithm described in this paper (A Technique for Drawing Directed Graphs), but I found that I cannot achieve the effect that graphviz can achieve. I am very confused about this. Has graphviz performed other optimizations?
Thank you for your interest in our work. The pseudocode above is high level. In the implementation, there are more heuristics and tweaks we found experimentally to improve performance. This amounts to improving the solver’s ability to get out of local minima, such as by untangling long edge chains. As an example, see the implementation of the weighted median computation. When there are ties in the median values, we could break them consistently, or we might try different possibilities, but in a way that does not immediately undo the progress in the next sweep over the layers of the graph (ranks) scanning in the opposite direction.
Since the code is published, you can read this for yourself. You may have already found a Wikipedia article or this book chapter. There are probably dozens of good papers on various aspects of this problem.
1 Like