Improved Lower Bounds for the 2-Page Crossing Numbers of $K_{m,n}$ and $K_n$ via Semidefinite Programming
From MaRDI portal
Publication:2910885
DOI10.1137/110852206zbMath1253.90183arXiv1110.4824WikidataQ56874345 ScholiaQ56874345MaRDI QIDQ2910885
Etienne de Klerk, Dimitrii 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
90C22: Semidefinite programming
90C25: Convex programming
68R10: Graph theory (including graph drawing) in computer science
05C10: Planar graphs; geometric and topological aspects of graph theory
57M15: Relations of low-dimensional topology with graph theory
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth, The optimal drawings of \(K_{5,n}\), Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation, The 2-page crossing number of \(K_{n}\), Book drawings of complete bipartite graphs, The Same Upper Bound for Both: The 2-page and the Rectilinear Crossing Numbers of then-Cube
Uses Software