Improved Lower Bounds on Book Crossing Numbers of Complete Graphs

DOI10.1137/120886777zbMath1273.90145arXiv1207.5701OpenAlexW1990541441WikidataQ56872309 ScholiaQ56872309MaRDI QIDQ2848524

Etienne de Klerk, Gelasio Salazar, Dimitrii V. Pasechnik

Publication date: 26 September 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

semidefinite programmingmaximum satisfiability problem2-page crossing numberbook crossing numbermaximum \(k\)-cutFrieze-Jerrum maximum-\(k\)-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

The Crossing Number of the Cone of a Graph, The Crossing Number of the Cone of a Graph, Book drawings of complete bipartite graphs, A note on the crossing number of the cone of a graph, On the crossing number of 2-page book drawings of \(K_n\) with prescribed number of edges in each page

Uses Software

• SageMath
• SDPT3
• YALMIP