The pagenumber of k-trees is O(k)
| Autor: | Joseph L. Ganley, Lenwood S. Heath |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Discrete mathematics
Book embedding Graph labeling k-trees Graph embedding Pagenumber Treewidth Applied Mathematics 0102 computer and information sciences 02 engineering and technology Strength of a graph 01 natural sciences Combinatorics 010201 computation theory & mathematics Graph power 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics 020201 artificial intelligence & image processing Graph toughness Complement graph MathematicsofComputing_DISCRETEMATHEMATICS Toroidal graph Mathematics |
| Zdroj: | Discrete Applied Mathematics. 109(3):215-221 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/s0166-218x(00)00178-5 |
| Popis: | A k-tree is a graph defined inductively in the following way: the complete graph Kk 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 Kk 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect