424 CHAPTER 13. HIERARCHICAL DRAWING ALGORITHMS
add vertices to the current layer which will reduce widthCurrent. If d
+
(v) < 1 then the
assignment of v to the current layer increases widthCurrent because it does not replace
any dummy vertices. This is an indication that widthCurrent can not be reduced further.
The min-width layering algorithm has the same time complexity as the longest-path
algorithm which has been shown to run in linear time [Ulm75]. Through an extensive
computational study Tarassov et al. have determined that the narrowest layerings are
found for 1 ≤ U BW ≤ 4 and 1 ≤ c ≤ 2. Thus, they propose to run the algorithm for
UBW ∈ {1, 2, 3, 4} and c ∈ {1, 2}, choose the narrowest of the eight layerings and apply to
it vertex-promotion