Improved lower bounds on book crossing numbers of complete graphs
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 bo...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2014
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/101539 http://hdl.handle.net/10220/18655 |
| Summary: | 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 ν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. We use semidefinite programming techniques to give
improved lower bounds on νk(Kn) for various values of k. We also use a maximum satisfiability
reformulation to obtain a computer-aided calculation of the exact value of νk(Kn) for several values
of k and n. Finally, we investigate the best construction known for drawing Kn in k pages, calculate
the resulting number of crossings, and discuss this upper bound in light of the new results reported
in this paper. |
|---|