## Fixed Parameter Algorithms for one-sided crossing minimization Revisited
Dujmovic, Vida and Fernau, Henning and Kaufmann, Michael
(2004)
Full text not available from this repository. ## AbstractWe 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.
Repository Staff Only: item control page References |