Global k-Level Crossing Reduction - Bachmaier, Christian; Brandenburg, Franz; Brunner, Wolfgang; Hübner, Ferdinand (Journal of Graph Algorithms and Applications, 2011)
<!----> Directed graphs are commonly drawn by a four phase framework introduced bySugiyama et al.in 1981. The vertices are placed on parallel horizontallevels. The edge routing between consecutive levels is computed by solvingone-sided 2-level crossing minimization problems, which are repeated in upand down sweeps over all levels. Crossing minimization problems aregenerally NP-hard. <!----> We introduce a global crossing reduction, which at any particular timeconsiders all crossings between all levels. Our approach is based on thesifting technique. It yields an improvement of 5 - 10% in the numberof crossings over the level-by-level one-sided 2-level crossing reductionheuristics. In addition, it avoids type 2 conflicts which are crossingsbetween edges whose endpoints are dummy vertices. This helps straighteninglong edges spanning many levels. Finally, the global crossing reductionapproach can directly be extended to cyclic, radial, and clustered levelgraphs achieving similar improvements. The running time is quadratic inthe size of the input graph, whereas the common level-by-level approachesare faster but operate on larger graphs with many dummy vertices for longedges. <!---->