Show simple item record

dc.contributor.authorGanley, Joseph L.en_US
dc.contributor.authorHeath, Lenwood S.en_US
dc.date.accessioned2013-06-19T14:35:42Z
dc.date.available2013-06-19T14:35:42Z
dc.date.issued1995-10-01
dc.identifierhttp://eprints.cs.vt.edu/archive/00000432/en_US
dc.identifier.urihttp://hdl.handle.net/10919/19944
dc.description.abstractA k-tree is a graph defined inductively in the following way: the complete graph K(sub-k) is a K-tree, and if G is a k-tree, then the graph resulting from adding a new vertex to k vertices inducing a K(sub-k) in G is also a k-tree. This paper examines the book embedding problem for k-trees. A book embedding of a graph maps the vertices onto a line along the spine of the book 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 in a valid book embedding. In this paper, it is proven that the pagenumber of a k-tree is at most k + 1. Furthermore, it is shown that there exist k-trees 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 known.en_US
dc.format.mimetypeapplication/postscripten_US
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen_US
dc.relation.ispartofHistorical Collection(Till Dec 2001)en_US
dc.titleThe Pagenumber of k-Trees is 0(k)en_US
dc.typeTechnical reporten_US
dc.identifier.trnumberTR-95-17en_US
dc.type.dcmitypeTexten_US
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000432/01/TR-95-17.ps


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record