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

DOI10.1137/110852206MaRDI QIDQ2910885zbMATH OpenOpenAlexWikidataFDO

Authors E. de Klerk, Dmitrii V. Pasechnik

Publication date 12 September 2012

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

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

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)

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.

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}\)

Cited in

(11)

• Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth
• 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
• New lower bounds on crossing numbers of \(K_{m,n}\) from semidefinite programming
• The 2-page crossing number of \(K_{n}\)
• Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• The \(2\)-page crossing number of \(K_n\)
• On the crossing number of \(K_{m,n}\)
• Book drawings of complete bipartite graphs
• The optimal drawings of \(K_{5,n}\)

Describes a project that uses

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)