(the following is the original commit message)
To ensure the optimal layout is choosen, it's important to try out
and compare a few different permutations.
First of all, layers are optimized. Those layers, that only contain
irrelevant artificial nodes are removed and all the others are shifted
in order to maintain simple layer indexing.
Then, using a simple hill climbing the permutation with the lowest
number of edge crossings is selected. After which a technique based
on computing barycenters for nodes and layers is used as a fallback
to ensure even the least optimal layout is still usable.
On top of all that, simple clustering based on the classification
obtained while preparing the graph is used to keep original nodes
somewhat separate from the artificial ones.
Ivan Krysak