Optimum embedding of complete graphs in books (Q1379820): Difference between revisions

The author gives an embedding of the complete graph with \(n\) vertices in a book of width \(n-3\) and \(\lceil n/2 \rceil\) pages---this improves an older result that needs width \(n\) for the same number of pages. An embedding of a graph in a book is an arrangement of the vertices along the spine and edges on the pages such that no edges residing on the same page cross. The width of the embedding is the maximum number of edges that cross any line perpendicular to the spine of the book on any page.