Improved lower bounds for the 2-page crossing numbers of K(m,n) and K(n) via semidefinite programming

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.

Article

Download

View Improved lower bounds for the 2-page crossing numbers of K(m,n) and K(n) via semidefinite programming