Crossing Minimisation Heuristics for 2-page Drawings

The minimisation of edge crossings in a book drawing of a graph G is one of important goals for a linear VLSI design, and the two-page crossing number of a graph G provides an upper bound for the standard planar crossing number. We propose several new heuristics for the 2-page drawing problem and test them on benchmark test sets like Rome graphs, Random Connected Graphs and some typical graphs. We get exact results of some structural graphs, and compare some of the experimental results with the one in paper [Cimikowski, Robert: Algorithms for the fixed linear crossing number problem, Discrete Applied Mathematics 122 (2002), 93–115].