The Pagenumber of k-Trees is 0(k)
| dc.contributor.author | Ganley, Joseph L. | en |
| dc.contributor.author | Heath, Lenwood S. | en |
| dc.contributor.department | Computer Science | en |
| dc.date.accessioned | 2013-06-19T14:35:42Z | en |
| dc.date.available | 2013-06-19T14:35:42Z | en |
| dc.date.issued | 1995-10-01 | en |
| dc.description.abstract | A 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 |
| dc.format.mimetype | application/postscript | en |
| dc.identifier | http://eprints.cs.vt.edu/archive/00000432/ | en |
| dc.identifier.sourceurl | http://eprints.cs.vt.edu/archive/00000432/01/TR-95-17.ps | en |
| dc.identifier.trnumber | TR-95-17 | en |
| dc.identifier.uri | http://hdl.handle.net/10919/19944 | en |
| dc.language.iso | en | en |
| dc.publisher | Department of Computer Science, Virginia Polytechnic Institute & State University | en |
| dc.relation.ispartof | Historical Collection(Till Dec 2001) | en |
| dc.rights | In Copyright | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.title | The Pagenumber of k-Trees is 0(k) | en |
| dc.type | Technical report | en |
| dc.type.dcmitype | Text | en |
Files
Original bundle
1 - 1 of 1