Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010)
Global k-Level Crossing Reduction
Christian Bachmaier, Franz J. Brandenburg, Wolfgang Brunner, and Ferdinand Hübner
Vol. 15, no. 5, pp. 631-659, 2011. Regular paper.
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.
Submitted: April 2010.
Reviewed: October 2010.
Revised: November 2010.
Accepted: April 2011.
Final: May 2011.
Published: October 2011.
Communicated by Md. Saidur Rahman and Satoshi Fujita
article (PDF)