The crossing number of a graph is the minimal number of edge crossings achievable in a drawing of the graph in the plane. The crossing numbers of complete and complete bipartite graphs are long standing open questions. In a 2-page drawing of a graph, all vertices are drawn on a circle, and no edge may cross the circle. It has been conjectured that the 2-page and normal crossing numbers coincide for complete and complete bipartite graphs. In this paper, we derive improved lower bounds on the 2-page crossing numbers for these two classes of graphs via semidefinite programming.
Citation
Preprint, Tilburg University, October 2011.