A tabu search algorithm for the bipartite drawing problem

Graphs are used to represent reality in several areas of knowledge. This has generated considerable interest in graph drawing algorithms. Arc crossing minimization is a fundamental aesthetic criterion to obtain a readable map of a graph. The problem of minimizing the number of arc crossings in a bipartite graph (BDP) is NP-complete. In this paper we present a Tabu Search (TS) scheme for the BDP. Several algorithms can be obtained with this scheme by implementing different evaluators in the move definitions. In this paper we propose two variants. Computational results are reported on a set of 300 randomly generated test problems. The two algorithms have been compared with the best heuristics published in the literature and, for limited-size instances, with the optimal solutions.