Arc crossing minimization in graphs with GRASP

Abstract

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.