Fixed Parameter Algorithms for one-sided crossing minimization Revisited

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.4656k + kn2) 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.