Width-restricted layering of acyclic digraphs with consideration of dummy nodes

This paper deals with the problem of finding graph layerings restricted to a given maximal width. However, other than previous approaches for width-re stricted layering, we take into account the space for dummy nodes, which ar e introduced by edges crossing a layer. The main result is that the problem of finding a width-restricted layering under consideration of dummy nodes is NP-complete even when all regular nodes have the same constant width and all dummy nodes have the same constant width. (C) 2002 Elsevier Science B. V All rights reserved.