13.3. LAYER ASSIGNMENT 419
model of the problem and a specific network simplex algorithm for solving it which although
not proven polynomial-time finds a layering with the minimum number of dummy vertices
reportedly fast [GKNV93].
Other parameters of a layering that reflect on the quality of the drawing are the width
and the height of a layering and the edge density between adjacent layers. The height of a
layering is the number of layers, and the width is the maximum number of vertices in a layer.
Usually these two parameters are used to approximate the dimensions of the final drawing.
When measuring the width of a layering the contribution of the dummy vertices may or may
not be taken into account. A more precise definition of the layering width tak