We like to draw hierarchical graphs in a way that represents the hierarchy in the graph. Vi can be placed on a vertical line such that all arcs point into one direction, say downwards. In a second step of the algorithm, the vertices in each layer Vi are permuted such that the overall number of crossings if the arcs are drawn as straight-lines should be minimized. We focus on the crossing minimization step. Even for only two layers, the crossing minimization problem is NP-hard.
Practitioners use the following method.
They fix the first layer of vertices and permute the second layer such that the number of crossings is small. Then the second layer is fixed, and the next layer is permuted. This problem can be transformed to a linear ordering problem, which can be solved very efficiently in practice via branch and cut . If our graph is not acyclic, we are interested in drawing the graph such that as many arcs as possible point in one direction. It turned out that the minimum feedback-arcset problem can be solved efficiently in practice using the methods of polyhedral combinatorics.