aiSee: Crossing Reduction

Crossing reduction

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.

» Next: Coordinate calculation
» Prev.: Rank assignment

Home
About
Examples
Free trial

Help
» FAQs
» Quick Guide
» User Manual
» Windows
» Mac
» GDL
» Options
» Changelog
» GDLedit

Store
Legal
Contact
Extras
Sitemap