Thumbnail
Access Restriction
Subscribed

Author Nikolov, Nikola S. ♦ Tarassov, Alexandre ♦ Branke, Jrgen
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2005
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Layer assignment ♦ Dummy vertices ♦ Hierarchical graph drawing ♦ Layered graphs ♦ Layering
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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 10


Open content in new tab

   Open content in new tab
Source: ACM Digital Library