Improved lower bounds for the 2-page crossing numbers of K(m,n) and K(n) via semidefinite programming
Etienne De Klerk(e.deklerkuvt.nl)
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.
Entry Submitted: 10/19/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|