Global k-Level Crossing Reduction

Abstract

Directed graphs are commonly drawn by a four phase framework introduced by Sugiyama et al.in 1981. The vertices are placed on parallel horizontal levels. The edge routing between consecutive levels is computed by solving one-sided 2-level crossing minimization problems, which are repeated in up and down sweeps over all levels. Crossing minimization problems are generally NP-hard. We introduce a global crossing reduction, which at any particular time considers all crossings between all levels. Our approach is based on the sifting technique. It yields an improvement of 5 - 10% in the number of crossings over the level-by-level one-sided 2-level crossing reduction heuristics. In addition, it avoids type 2 conflicts which are crossings between edges whose endpoints are dummy vertices. This helps straightening long edges spanning many levels. Finally, the global crossing reduction approach can directly be extended to cyclic, radial, and clustered level graphs achieving similar improvements. The running time is quadratic in the size of the input graph, whereas the common level-by-level approaches are faster but operate on larger graphs with many dummy vertices for long edges.