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  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  are exhibited.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- Fixed Parameter Algorithms for one-sided crossing minimization Revisited
- Springer Berlin Heidelberg
ec4u, Neuer Inhalt/© ITandMEDIA