Is this graph problem NP-hard / NP-complete? I have a certain kind of graphs. They are DAGs similar to dependency graphs but strictly hierarchical, that is, each node belong to a certain level in the hierarchy and cannot be moved up or down when the graph is laid out onto a plane. The nodes can be arbitrarily exchanged with others in the same level.

Here's an example:



The problem:

Find an ordering (permutation) of the nodes in each level of the hierarchy such that the total number of edge crossings is minimal.

The problem could be, I suppose, rephrased as a decision problem: Given an ordering of nodes in each level, decide whether that ordering is minimal in terms of number of edge crossings.

For example, in the above graph embedding there are 3 edge crossings, however, by reordering the nodes in a certain way we obtain an embedding that only has 1 edge crossing (I believe this is minimum for this particular graph):



(Nodes that have been moved are highlighted.)

The question:

Is this problem NP-hard? I'm having a hard time finding correspondence to one of the more well-known NP-hard/NP-complete problems but at the same time I'm having a hard time finding a polytime solution.
Turns out this is indeed an NP-complete/NP-hard problem according to wikipedia and Eades et al.