Please use this identifier to cite or link to this item:

`https://hdl.handle.net/10356/96333`

Title: | Improved lower bounds for the 2-page crossing numbers of Km,n and Kn via semidefinite programming |

Authors: | Klerk, E. de. Pasechnik, Dmitrii V. |

Issue Date: | 2012 |

Source: | Klerk, 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. |

Series/Report no.: | SIAM journal on optimization |

Abstract: | It 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$. |

URI: | https://hdl.handle.net/10356/96333 http://hdl.handle.net/10220/10215 |

ISSN: | 1052-6234 |

DOI: | 10.1137/110852206 |

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. |

Fulltext Permission: | open |

Fulltext Availability: | With Fulltext |

Appears in Collections: | SPMS Journal Articles |

###### Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

101. Improved lower bounds.pdf | 256.79 kB | Adobe PDF | View/Open |

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.