Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Fourth International Workshop on Algorithms and Computation (WALCOM 2010)
DOI: 10.7155/jgaa.00242
Global k-Level Crossing Reduction
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.
|
Journal Supporters
|