13.3. LAYER ASSIGNMENT 429
Although the longest-path algorithm finds layerings with the minimum number of layers
and the Coffman-Graham algorithm finds layerings with a pre-specified maximum number
of vertices in a layer, their layerings typically lead to drawings which occupy large drawing
area and have too many long edges.
For a compact layering, the network simplex algorithm of Gansner et al., described in
Section 13.3.2, is probably the best fast solution. It finds layerings with the minimum
number of dummy vertices which are also very compact in general. However, there are
particular patterns in graph that may make the network simplex layering either too wide or
too long. The branch-and-cut algorithm of Healy and Nikolov, outlined in Section 13.3.2, ...