Back to Search
Start Over
Improved lower bounds on book crossing numbers of complete graphs
- Source :
- SIAM J. Discrete Math., 27(2013), 619-633
- Publication Year :
- 2012
-
Abstract
- A "book with k pages" consists of a straight line (the "spine") and k half-planes (the "pages"), such that the boundary of each page is the spine. If a graph is drawn on a book with k pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a k-page drawing). The k-page crossing number nu_k(G) of a graph G is the minimum number of crossings in a k-page drawing of G. In this paper we investigate the k-page crossing numbers of complete graphs K_n. We use semidefinite programming techniques to give improved lower bounds on nu_k(K_n) for various values of k. We also use a maximum satisfiability reformulation to calculate the exact value of nu_k(K_n) for several values of k and n. Finally, we investigate the best construction known for drawing K_n in k pages, calculate the resulting number of crossings, and discuss this upper bound in the light of the new results reported in this paper.<br />Comment: pdfLaTeX, 26 pages
- Subjects :
- Mathematics - Combinatorics
05C10, 90C90
Subjects
Details
- Database :
- arXiv
- Journal :
- SIAM J. Discrete Math., 27(2013), 619-633
- Publication Type :
- Report
- Accession number :
- edsarx.1207.5701
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1137/120886777