Abstract
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.
Original language | English |
---|---|
Article number | 1180618 |
Journal | ACM Journal of Experimental Algorithmics |
Volume | 10 |
DOIs | |
Publication status | Published - 2005 |
Keywords
- Dummy vertices
- G.1.1 [interpolation]
- G.2 [approximation]
- Hierarchical graph drawing
- Layer assignment
- Layered graphs
- Layering