A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction
Forster, Michael (2004) A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 206-216 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_22).
Full text not available from this repository.
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  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