Abstract
This work contributes to the wide research area of visualization of hierarchical graphs. We present a new polynomial-time heuristic which can be integrated into the Sugiyama method for drawing hierarchical graphs. Our heuristic, which we call Promote Layering (PL), is applied to the output of the layering phase of the Sugiyama method. PL is a simple and easy to implement algorithm which decreases the number of so-called dummy (or virtual) nodes in a layered directed acyclic graph. In particular, we propose applying PL after the longest-path layering algorithm and we present an extensive empirical evaluation of this layering technique.
Original language | English |
---|---|
Pages (from-to) | 848-860 |
Number of pages | 13 |
Journal | Discrete Applied Mathematics |
Volume | 154 |
Issue number | 5 SPEC. ISS. |
DOIs | |
Publication status | Published - 1 Apr 2006 |
Keywords
- Graph drawing
- Layered directed acyclic graph
- Layering algorithm