In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes

Nikola S. Nikolov, Alexandre Tarassov, Jürgen Branke

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Article number1180618
JournalACM Journal of Experimental Algorithmics
Volume10
DOIs
Publication statusPublished - 2005

Keywords

  • Dummy vertices
  • G.1.1 [interpolation]
  • G.2 [approximation]
  • Hierarchical graph drawing
  • Layer assignment
  • Layered graphs
  • Layering

Fingerprint

Dive into the research topics of 'In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes'. Together they form a unique fingerprint.

Cite this