Book embeddings of graphs
Robin Leigh Blankenship · Civil War Book Review · 2003
We use a structural theorem of Robertson and Seymour to show that for every minor-closed class of graphs, other than the class of all graphs, there is a number k such that every member of the class can be embedded in a book with k pages. Book embeddings of graphs with relation to surfaces, vertex extensions, clique-sums and r-rings are combined into a single book embedding of a graph in the minor-closed class. The effects of subdividing a complete graph and a complete bipartite graph with respect to book thickness are studied. We prove that if n ≥ 3, then the book thickness of Kn is the ceiling of (n/2). We also prove that for each m and B, there exists an integer N such that for all n ≥ N, the book thickness of the graph obtained from subdividing each edge of Kn exactly m times has book thickness at least B. Additionally, there are corresponding theorems for complete bipartite graphs.