This pass calculates a good order of the nodes within levels so as to avoid edge crossings. The first step is to separate connected components of the graph and to handle each component separately.
The crossing reduction algorithm calculates the weights of the nodes in keeping with the possible crossings to the left and the right, and reorders the nodes of a level according to these weights. The ordering of nodes within one level influences the weights of the adjacent levels, consequently this is performed iteratively until a user-defined maximum is reached or no more improvements are recognized. This is phase 1 of the crossing reduction.
If the weights of some nodes are equal a permutation of
these nodes is tried. Sometimes a permutation enables crossings to be
reduced even further (optional phase 2 of crossing reduction, see graph
attribute crossing_phase2).
However, the final result needn't necessarily be optimal as crossing
reduction is only a heuristic.
There are four possibilities to calculate weights for
crossing heuristics. The default weights are barycenter weights
[STM81], while mediancenter weights
[GNV88] are sometimes more appropriate,
especially if the average degree (number of edges) of nodes is small.
barymedian weights are the combination of barycenter
and mediancenter, where barycenter is considered first and mediancenter
is only used for nodes whose barycenter weights are equal. Conversely,
medianbary weights are the combination of barycenter and
mediancenter, where mediancenter is considered first. The weights can
be selected interactively in the Layout dialog box,
or statically in the GDL specification, see graph attribute
crossing_weight.
Finally, a local optimization phase tries to improve the
layout by exchanging directly neighbored nodes. See graph attribute
crossing_optimization.