Welcome to the InfoSci Platform
Page Number and Graph Treewidth

Page Number and Graph Treewidth

Li Xianglu
Copyright: © 2012 |Pages: 7
ISBN13: 9781466602700|ISBN10: 1466602708|EISBN13: 9781466602717
DOI: 10.4018/978-1-4666-0270-0.ch018
Cite Chapter Cite Chapter

MLA

Xianglu, Li. "Page Number and Graph Treewidth." Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends, edited by Peng-Yeng Yin, IGI Global, 2012, pp. 326-332. https://doi.org/10.4018/978-1-4666-0270-0.ch018

APA

Xianglu, L. (2012). Page Number and Graph Treewidth. In P. Yin (Ed.), Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends (pp. 326-332). IGI Global. https://doi.org/10.4018/978-1-4666-0270-0.ch018

Chicago

Xianglu, Li. "Page Number and Graph Treewidth." In Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends, edited by Peng-Yeng Yin, 326-332. Hershey, PA: IGI Global, 2012. https://doi.org/10.4018/978-1-4666-0270-0.ch018

Export Reference

Mendeley
Favorite

Abstract

Book-embedding of graph G involves embedding its vertices along the spine of the book and assigning its edges to pages of the book such that no two edges cross on the same page. The pagenumber of G is the minimum number of pages in a book-embedding of G. In this paper, the authors also examine the treewidth TW(G), which is the minimum k such that G is a subgraph of a k-tree. The authors then study the relationship between pagenumber and treewidth. Results show that PN(G)=TW(G), which proves a conjecture of Ganley and Heath showing that some known upper bounds for the pagenumber can be improved.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.