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 , 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 [12] and Finnocchi [1,2,6], while it compares well in terms of crossing number. It is also easy to implement.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_22
Classifications: M Methods > M.500 Layered
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
URI: http://gdea.informatik.uni-koeln.de/id/eprint/588

Actions (login required)

View Item View Item