The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
Page Number and Graph Treewidth
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.
Related Content
|
Pawan Kumar, Mukul Bhatnagar, Sanjay Taneja.
© 2024.
26 pages.
|
|
Kapil Kumar Aggarwal, Atul Sharma, Rumit Kaur, Girish Lakhera.
© 2024.
19 pages.
|
|
Mohammad Kashif, Puneet Kumar, Sachin Ghai, Satish Kumar.
© 2024.
15 pages.
|
|
Manjit Kour.
© 2024.
13 pages.
|
|
Sanjay Taneja, Reepu.
© 2024.
19 pages.
|
|
Jaspreet Kaur, Ercan Ozen.
© 2024.
28 pages.
|
|
Hayet Kaddachi, Naceur Benzina.
© 2024.
25 pages.
|
|
|