Improved lower bounds on book crossing numbers of complete graphs
Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

A book with k pages consists of a straight line (the spine) and k halfplanes (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 kpage book drawing (or simply a kpage drawing). The kpage crossing number νk(G) of a graph G is the minimum number of crossings in a kpage drawing of G. In this paper we investigate the kpage 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 computeraided 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. © 2013 Society for Industrial and Applied Mathematics.
publication date
published in
Research
keywords

2page crossing number; Book crossing number; FriezeJerrum maximumkcut bound; Maximum kcut; Maximum satisfiability problem; Semidefinite programming Crossing number; FriezeJerrum maximumkcut bound; Maximum kcut; Maximum satisfiability problems; Semidefinite programming; Formal logic; Mathematical programming; Graph theory
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue