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-restricted layering, we take into account the space for dummy nodes, which are 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 al regular nodes have the same constant width and all dummy nodes have the same constant width.