Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/96333
DC FieldValueLanguage
dc.contributor.authorKlerk, E. de.en
dc.contributor.authorPasechnik, Dmitrii V.en
dc.date.accessioned2013-06-12T01:55:50Zen
dc.date.accessioned2019-12-06T19:29:09Z-
dc.date.available2013-06-12T01:55:50Zen
dc.date.available2019-12-06T19:29:09Z-
dc.date.issued2012en
dc.identifier.citationKlerk, E. d. & Pasechnik, D. V. (2012). Improved Lower Bounds for the 2-Page Crossing Numbers of Km,n and Kn via Semidefinite Programming. SIAM Journal on Optimization, 22(2), 581-595.en
dc.identifier.issn1052-6234en
dc.identifier.urihttps://hdl.handle.net/10356/96333-
dc.identifier.urihttp://hdl.handle.net/10220/10215en
dc.description.abstractIt has long been conjectured that the crossing numbers of the complete bipartite graph $K_{m,n}$ and of the complete graph $K_n$ equal $Z(m,n):=\bigl\lfloor\frac{n}{2}\bigr\rfloor \bigl\lfloor\frac{n-1}{2}\bigr\rfloor \bigl\lfloor\frac{m}{2}\bigr\rfloor \bigl\lfloor\frac{m-1}{2}\bigr\rfloor$ and $Z(n):=\frac{1}{4} \bigl\lfloor\frac{n}{2}\bigr\rfloor \bigl\lfloor\frac{n-1}{2}\bigr\rfloor \bigl\lfloor\frac{n-2}{2}\bigr\rfloor \bigl\lfloor\frac{n-3}{2}\bigr\rfloor$, 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 $\nu_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) $\nu_2(K_{m,n}) \stackrel{?}{=} Z(m,n)$ and (II) $\nu_2(K_n) \stackrel{?}{=} Z(n)$. It is known that (I) holds for $\min\{m,n\} \le 6$, and that (II) holds for $n \le 14$. In this paper we prove that (I) holds asymptotically (that is, $\lim_{n\to\infty} \nu_2(K_{m,n})/Z(m,n) =1$) for $m=7$ and $8$. We also prove (II) for $15 \le n \le 18$ and $n \in \{20,24\}$, and establish the asymptotic estimate $\lim_{n\to\infty} \nu_2(K_{n})/Z(n) \ge 0.9253.$ The previous best-known lower bound involved the constant $0.8594$.en
dc.language.isoenen
dc.relation.ispartofseriesSIAM journal on optimizationen
dc.rights© 2012 Society for Industrial and Applied Mathematics. This paper was published in SIAM Journal on Optimization and is made available as an electronic reprint (preprint) with permission of Society for Industrial and Applied Mathematics. The paper can be found at the following official DOI: [http://dx.doi.org/10.1137/110852206]. One print or electronic copy may be made for personal use only. Systematic or multiple reproduction, distribution to multiple locations via electronic or other means, duplication of any material in this paper for a fee or for commercial purposes, or modification of the content of the paper is prohibited and is subject to penalties under law.en
dc.titleImproved lower bounds for the 2-page crossing numbers of Km,n and Kn via semidefinite programmingen
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen
dc.identifier.doi10.1137/110852206en
dc.description.versionPublished versionen
item.fulltextWith Fulltext-
item.grantfulltextopen-
Appears in Collections:SPMS Journal Articles
Files in This Item:
File Description SizeFormat
101. Improved lower bounds.pdf256.79 kBAdobe PDF