Optimization Online


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

Etienne De Klerk(e.deklerk***at***uvt.nl)
Dmitrii V. Pasechnik(dima***at***ntu.edu.sg )

Abstract: 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.

Keywords: 2-page crossing number, book crossing number, semidefinite programming, maximum cut, Goemans-Williamson max-cut bound

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Category 3: Combinatorial Optimization

Citation: Preprint, Tilburg University, October 2011.

Download: [PDF]

Entry Submitted: 10/19/2011
Entry Accepted: 10/19/2011
Entry Last Modified: 10/19/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society