Thumbnail
Access Restriction
Subscribed

Author Bachmaier, Christian ♦ Brunner, Wolfgang ♦ Gleiner, Andreas
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2012
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Crossing reduction ♦ Sugiyama framework ♦ Global approach ♦ Level graphs ♦ No dummy vertices
Abstract Directed graphs are commonly drawn by the Sugiyama algorithm where first vertices are placed on distinct hierarchical levels, and second vertices on the same level are permuted to reduce the overall number of crossings. Separating these two phases simplifies the algorithms but diminishes the quality of the result. We introduce a combined leveling and crossing reduction algorithm based on sifting, which prioritizes few crossings over few levels. It avoids type 2 conflicts, which are crossings of edges whose endpoints are dummy vertices. This helps straightening long edges spanning many levels. The obtained running time is roughly quadratic in the size of the input graph and independent of dummy vertices.
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 2012-10-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 17
Page Count 23
Starting Page 1.1
Ending Page 1.23


Open content in new tab

   Open content in new tab
Source: ACM Digital Library