Thumbnail
Access Restriction
Subscribed

Author Stallmann, Matthias F.
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 Barycenter heuristic ♦ Crossing minimization ♦ Sifting heuristic
Abstract Extensive research over the last 20 or more years has been devoted to the problem of minimizing the total number of crossings in layered directed acyclic graphs (dags). Algorithms for this problem are used for graph drawing, to implement one of the stages in the multistage approach proposed by Sugiyama et al. [1981]. In some applications, such as minimizing the deleterious effects of crosstalk in VLSI circuits, it may be more appropriate to minimize the maximum number of crossings over all the edges. We refer to this as the bottleneck crossing problem. This article proposes a new heuristic, maximum crossings edge (MCE), designed specifically for the bottleneck problem. It is no surprise that MCE universally outperforms other heuristics with respect to bottleneck crossings. What is surprising, and the focus of this article, is that, in many settings, the MCE heuristic excels at minimizing the total number of crossings. Experiments on sparse graphs support the hypothesis that MCE gives better results (vis a vis barycenter) when the maximum degree of the dag is large. In contrast to barycenter, the number of crossings yielded by MCE is further reduced as runtime is increased. Even better results are obtained when the two heuristics are combined and/or barycenter is followed by the sifting heuristic reported in Matuszewski et al. [1999].
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-07-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 17
Page Count 30
Starting Page 1.1
Ending Page 1.30


Open content in new tab

   Open content in new tab
Source: ACM Digital Library