Optimum embedding of complete graphs in books (Q1379820)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimum embedding of complete graphs in books |
scientific article |
Statements
Optimum embedding of complete graphs in books (English)
0 references
4 May 1999
0 references
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.
0 references
embedding
0 references
complete graph
0 references
book
0 references