The pagenumber of k-trees is O(k)

A k-tree is a graph defined inductively in the following way: the complete graph K-k is a k-tree, and if G is a k-tree, then the graph resulting from adding a new vertex adjacent to k vertices inducing a K-k in G is also a k- tree. This paper examines the book-embedding problem for k-trees. A book em bedding of a graph maps the vertices onto a line along the spine of the boo k and assigns the edges to pages of the book such that no two edges on the same page cross. The pagenumber of a graph is the minimum number of pages i n a valid book embedding. In this paper, it is proven that the pagenumber o f a k-tree is at most k + 1. Furthermore, it is shown that there exist k-tr ees that require k pages. The upper bound leads to bounds on the pagenumber of a variety of classes of graphs for which no bounds were previously know n. (C) 2001 Elsevier Science B.V. All rights reserved.