An evolutionary algorithm for the 2-page crossing number problem

Many real-life scheduling, routing and location problems can be formulated as combinatorial optimization problems whose goal is to find a linear layout of an input graph in such a way that the number of edge crossings is minimized. The minimization of edge crossings in a book drawing of a graph is one of the important goals for a linear VLSI design. In this paper, we propose an evolutionary algorithm for crossing number minimization in the 2-page book drawing of graphs in which the initial population is generated by depth first search method with edge length strategy for dividing the edges into two pages. An important feature of the evolutionary process of this algorithm is that it improves the number of crossings by exploring various depth first search trees of the graph instead of applying the usual crossover operator. Minor disturbances are created by the mutation operator. The experiments done on benchmark graphs and some standard graphs show that the algorithm achieves the crossing numbers that are either optimal or known to be the best so far, in much lesser time as compared with the existing techniques.