## A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction
Forster, Michael
(2004)
Full text not available from this repository. ## AbstractThe 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.
Repository Staff Only: item control page References |