Graph layering by promotion of nodes

Nikola S. Nikolov, Alexandre Tarassov

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)848-860
Number of pages13
JournalDiscrete Applied Mathematics
Volume154
Issue number5 SPEC. ISS.
DOIs
Publication statusPublished - 1 Apr 2006

Keywords

  • Graph drawing
  • Layered directed acyclic graph
  • Layering algorithm

Fingerprint

Dive into the research topics of 'Graph layering by promotion of nodes'. Together they form a unique fingerprint.

Cite this