  We consider the problem of layering general directed graphs under height and
possibly also width constraints. Given a directed graph G = (V,A) and a maximal
height, we propose a layering approach that minimizes a weighted sum of the
number of reversed arcs, the arc lengths, and the width of the drawing. We call
this the Compact Generalized Layering Problem (CGLP). Here, the width of a
drawing is defined as the maximum sum of the number of vertices placed on a
layer and the number of dummy vertices caused by arcs traversing the layer. The
CGLP is NP-hard. We present two MIP models for this problem. The first one
(EXT) is our extension of a natural formulation for directed acyclic graphs as
suggested by Healy and Nikolov. The second one (CGL) is a new formulation based
on partial orderings. Our computational experiments on two benchmark sets show
that the CGL formulation can be solved much faster than EXT using standard
commercial MIP solvers. Moreover, we suggest a variant of CGL, called MML, that
can be seen as a heuristic approach. In our experiments, MML clearly improves
on CGL in terms of running time while it does not considerably increase the
average arc lengths and widths of the layouts although it solves a slightly
different problem where the dummy vertices are not taken into account.
