Fixed Parameter Algorithms for one-sided crossing minimization Revisited

Dujmović, Vida and Fernau, Henning and Kaufmann, Michael (2004) Fixed Parameter Algorithms for one-sided crossing minimization Revisited. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 332-344(Official URL:

Full text not available from this repository.


We exhibit a small problem kernel for the problem one-sided crossing minimization which plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we improve on the search tree algorithm developed in [5] and derive an O(1.4656^{k} + kn^2) algorithm for this problem, where k upperbounds the number of tolerated crossings of straight lines involved in the drawings of an n-vertex graph. Relations of this graph-drawing problem to the algebraic problem of finding a weighted linear extension of an ordering similar to [7] are exhibited.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_31
Classifications: G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered

Actions (login required)

View Item View Item