Optimum embedding of complete graphs in books (Q1379820): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:08, 5 March 2024
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