In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes
Nikola S. Nikolov, Alexandre Tarassov, Jürgen Branke · ACM Journal of Experimental Algorithmics · 2005
We propose two fast heuristics for solving the NP-hard problem of graph layering with the minimum width and consideration of dummy nodes. Our heuristics can be used at the layer-assignment phase of the Sugiyama method for drawing of directed graphs. We evaluate our heuristics by comparing them to the widely used fast-layering algorithms in an extensive computational study with nearly 6000 input graphs. We also demonstrate how the well-known longest-path and Coffman--Graham algorithms can be used for finding narrow layerings with acceptable aesthetic properties.