434 CHAPTER 13. HIERARCHICAL DRAWING ALGORITHMS
general crossing minimization problem, where permutations for both layers that minimize
the number of crossings are required, is NP -hard [GJ83]; even if one layer is fixed, the
problem still remains N P -hard [EW94]. To counter these apparently negative results,
several heuristic and exact methods have been proposed.
While we will mainly be concerned with algorithms that find a drawing with few crossings,
the decision version of the problem [GJ83, EW94] also is of interest. In particular, fixed-
parameter tractable algorithms have been developed to answer the question of whether an
ordering of the vertices on one “shore” of a bipartite graph admits a k-crossing (or less)
solution when the vertices of