Heuristic crossing minimisation algorithms for the two-page drawing problem

The minimisation of edge crossings in a book drawing of a graph G is one of the 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 two-page drawing problem, and test them on benchmark test suites, Rome graphs and Random Connected Graphs. We also test some typical graphs, and get some exact results. The results for some circulant graphs are better than the one presented by Cimikowski. We have a conjecture for cartesian graphs, supported by our experimental results, and provide direct methods to get optimal solutions for 3- or 4-row meshes and Halin graphs.