Improved lower bounds for the 2-page crossing numbers of K_m,n and K_n via semidefinite programming

DOI10.1137/110852206zbMATH Open1253.90183arXiv1110.4824OpenAlexW3103545947WikidataQ56874345 ScholiaQ56874345MaRDI QIDQ2910885FDOQ2910885

Authors: E. de Klerk, Dmitrii V. Pasechnik 

Publication date: 12 September 2012

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: It has been long conjectured that the crossing numbers of the complete bipartite graph K_{m,n} and of the complete graph K_n equal Z(m,n) (the value conjectured by Zarankiewicz, who came up with a drawing reaching this value) and Z(n) :=Z(n,n-2)/4, respectively. In a 2-page drawing of a graph, the vertices are drawn on a straight line (the spine), and each edge is contained in one of the half-planes of the spine. The 2-page crossing number v_2(G) of a graph G is the minimum number of crossings in a 2-page drawing of G. Somewhat surprisingly, there are 2-page drawings of K_{m,n} (respectively, K_n) with exactly Z(m, n) (respectively, Z(n)) crossings, thus yielding the conjectures (I) v_2(Km,n) =Z(m,n), and (II) v_2(Kn) = Z(n). It is known that (I) holds for min{m, n} <=6, and that (II) holds for n<=14. In this paper we prove that (I) holds asymptotically (that is, lim_n v_2 (K_{m,n})/Z (m, n) = 1) for m=7 and 8. We also prove (II) for 15<=n<=18 and n=20,24, and establish the asymptotic estimate lim_n v_2(K_n)/Z(n) >= 0.9253. The previous best-known lower bound involved the constant 0.8594.

Full work available at URL: https://arxiv.org/abs/1110.4824

Recommendations

• Improved Bounds for the Crossing Numbers of Km,n and Kn
• The \(2\)-page crossing number of \(K_n\)
• The 2-page crossing number of \(K_{n}\)
• Book drawings of complete bipartite graphs
• On the crossing number of \(K_{m,n}\)

zbMATH Keywords

maximum cut2-page crossing numberbook crossing numberGoemans-Williamson max-cut bound

Mathematics Subject Classification ID

Convex programming (90C25) Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Relations of low-dimensional topology with graph theory (57M15)

Cited In (10)

• The \(2\)-page crossing number of \(K_n\)
• Book drawings of complete bipartite graphs
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• On the crossing number of \(K_{m,n}\)
• The optimal drawings of \(K_{5,n}\)
• The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
• Improved lower bounds on book crossing numbers of complete graphs
• The 2-page crossing number of \(K_{n}\)
• Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation

Uses Software

• SDPT3
• YALMIP

This page was built for publication: Improved lower bounds for the 2-page crossing numbers of \(K_{m,n}\) and \(K_n\) via semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910885)