A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction


The one-sided two-level crossing reduction problem is an important problem in hierarchical graph drawing. Because of its NP-hardness there are many heuristics, such as the well-known barycenter and median heuristics. We consider the constrained one-sided two-level crossing reduction problem, where the relative position of certain vertex pairs on the second level is fixed. Based on the barycenter heuristic, we present a new algorithm that runs in quadratic time and generates fewer crossings than existing simple extensions. It is significantly faster than an advanced algorithm by Schreiber [12] and Finnocchi [1, 2, 6], while it compares well in terms of crossing number. It is also easy to implement.

János Pach (ed.), Proc. Graph Drawing, GD 2004, Lecture Notes in Computer Science 3383:206–216, Springer