|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 13 of 30 found articles
| Title: |
Arc crossing minimization in graphs with GRASP |
| Author: |
Marti, Rafael |
| Appeared in: |
IIE transactions |
| Paging: | Volume 33 (2001) nr. 10 pages 913-919 |
| Year: |
2001-10-01 |
| Contents: |
Graphs are commonly used to represent information in many fields of science and engineering. Automatic drawing tools generate comprehensible graphs from data, taking into account a variety of properties, enabling users to see important relationships in the data. The goal of limiting the number of arc crossings is a well-admitted criterion for a good drawing. In this paper, we present a Greedy Randomized Adaptive Search Procedure (GRASP) for the problem of minimizing are crossings in graphs. Computational experiments with 200 graphs with up to 350 vertices are presented to assess the merit of the method. We show that simple heuristics are very fast but result in inferior solutions, while high-quality solutions have been found with complex meta-heuristics but demand an impractical amount of computer time. The proposed GRASP algorithm is better in speed than complex meta-heuristics and in quality than simple heuristics. Thus, it is a clear candidate for practical implementations in graph drawing software systems. |
| Publisher: |
Taylor & Francis |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 13 of 30 found articles
| << previous | next >> |