Phase 2: Sorting of nodes next up previous
Next: Phase 3: Positioning of Up: Layout Phases Previous: Phase 1: Partitioning into

Phase 2: Sorting of nodes

For each node v, a relative position P(v) within its layer has to be calculated, such that there are only few edge crossings. Since the hierarchy is proper, the number of crossings c originated by the edges tex2html_wrap_inline2582 between two adjacent layers tex2html_wrap_inline2584 and tex2html_wrap_inline2586 can be easily determined by a plane sweep algorithm [Sa94] in time tex2html_wrap_inline2588 . However, the problem of finding permutations of the sequences tex2html_wrap_inline2590 and tex2html_wrap_inline2592 to get a minimal number of crossings is tex2html_wrap_inline2478 -complete [GaJo83]. Methods to solve the crossing problem can be found in [STT81, EaWo86, EaKe86, EaSu90, Sa94, JuMu96]. In practice, the most successful algorithm is the layer-by-layer-sweep:

(1)  		 while  the crossing number is not satisfactory do 

(2) for each layer tex2html_wrap_inline2584 from i = 1 to n do

(3) for each tex2html_wrap_inline2602 do

(4) Calculate weight tex2html_wrap_inline2604 ;

(5) od

(6) Sort the nodes of tex2html_wrap_inline2584 according to the weight tex2html_wrap_inline2604 ;

(7) od

(8) for each tex2html_wrap_inline2584 from i = n to 1 do ... similar with tex2html_wrap_inline2616 od

(9) od

The first traversal (line (2)-(7)) is a top down traversal, the second (line (8)) is a bottom up traversal. Other variations of this method sweep only top down or only bottom up, or from the center outwards. [Sa94] describes a variation with limited backtracking: if a sweep did not reduce the number of crossings, the old configuration is taken. The crucial point is the selection of the weights tex2html_wrap_inline2618 and tex2html_wrap_inline2620 . [STT81] proposes the barycenter weight (P(w) is the relative position of the node w in the predecessor or successor layer, respectively):


[EaWo86, GKN93] propose the median of the sequence tex2html_wrap_inline2626 of predecessors of a node v:


We also made experiments with combinations of both, using


A method of calculating the optimal permutation of two layers where one layer is fixed was proposed in [JuMu96]. Assume that the permutation of tex2html_wrap_inline2590 is fixed, and a permutation of tex2html_wrap_inline2592 should be calculated. Let tex2html_wrap_inline2634 denote the number of crossings among edges adjacent to tex2html_wrap_inline2636 in a permutation of tex2html_wrap_inline2592 where tex2html_wrap_inline2640 . Let tex2html_wrap_inline2642 if tex2html_wrap_inline2640 , and tex2html_wrap_inline2646 otherwise. Then the number of crossings of a permutation of tex2html_wrap_inline2592 can be described as


The optimal permutation of tex2html_wrap_inline2592 can be found by calculating tex2html_wrap_inline2652 such that C is minimal, subject to (1) tex2html_wrap_inline2656 for tex2html_wrap_inline2658 , and (2) tex2html_wrap_inline2660 for tex2html_wrap_inline2662 . The "3-cycle constraints" (1) guarantee that the result describes a valid permutation. This linear integer programming problem can be solved by a variation of the branch and cut algorithm [JuMu96]. This method is suitable up to tex2html_wrap_inline2664 , but it is much too slow for larger graphs.

Statistical experiments [JuMu96, Sa96b] show that apart from the optimal method for two layers where one is fixed, the best heuristic is tex2html_wrap_inline2666 with tex2html_wrap_inline2668 , followed by tex2html_wrap_inline2670 , and at last by tex2html_wrap_inline2672 . These methods are also closer to the optimum and faster than various greedy or stochastic methods described in [EaKe86, JuMu96]. However, this experimental result does not hold if there are more than two layers, and a layer-by-layer-sweep is used. Firstly, a sweep with the two-layer-optimal algorithm does not calculate the optimal crossing number of the whole multi-layer-graph since a nonoptimal permutation of some adjacent layers might produce less crossings than a situation where the first layer is optimal, but the other layers are only optimal derived from the first layer. Secondly, it is not obvious which of tex2html_wrap_inline2674 and tex2html_wrap_inline2666 produces the fewest crossings in a multi-layer-graph: there are many examples where any of the three is the best.

next up previous
Next: Phase 3: Positioning of Up: Layout Phases Previous: Phase 1: Partitioning into

Georg Sander
Thu Aug 1 15:27:34 PDT 1996