Improved Lower Bounds for the 2-Page Crossing Numbers of $K_{m,n}$ and $K_n$ via Semidefinite Programming

DOI10.1137/110852206zbMath1253.90183arXiv1110.4824OpenAlexW3103545947WikidataQ56874345 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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (6)

The 2-page crossing number of \(K_{n}\) ⋮ Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth ⋮ Book drawings of complete bipartite graphs ⋮ The optimal drawings of \(K_{5,n}\) ⋮ Bound for the 2-page fixed linear crossing number of hypercube graph via SDP relaxation ⋮ The Same Upper Bound for Both: The 2-page and the Rectilinear Crossing Numbers of then-Cube

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