A hybrid simulated annealing algorithm for the Bipartite Crossing Number Minimization Problem

The bipartite crossing number of a bipartite graph is the minimum number of crossings of edges when the partitions are placed on two parallel lines and edges are drawn as straight line segments between the lines. In this paper, a simulated annealing algorithm is designed which exploits the relationship between the linear arrangement problem and the bipartite crossing number minimization problem. The initial ordering of the vertices is provided by the spectral sequencing technique. Extensive tests on several benchmark graphs show that in a majority of the cases there is a considerable improvement in the crossing number when compared with the best known results.