A survey on book-embedding of planar graphs |
| |
Authors: | Xiaxia GUAN Chuxiong WU Weihua YANG Jixiang MENG |
| |
Affiliation: | 1. College of Mathematics, Taiyuan University of Technology, Taiyuan 030024, China2. College of Mathematics and System Science, Xinjiang University, Urumqi 830046, China |
| |
Abstract: | The book-embedding problem arises in several area, such as very large scale integration (VLSI) design and routing multilayer printed circuit boards (PCBs). It can be used into various practical application fields. A book embedding of a graph G is an embedding of its vertices along the spine of a book, and an embedding of its edges to the pages such that edges embedded on the same page do not intersect. The minimum number of pages in which a graph G can be embedded is called the pagenumber or book-thickness of the graph G. It is an important measure of the quality for book-embedding. It is NP-hard to research the pagenumber of book-embedding for a graph G. This paper summarizes the studies on the book-embedding of planar graphs in recent years. |
| |
Keywords: | Book embedding planar graphs pagenumber |
|
| 点击此处可从《Frontiers of Mathematics in China》浏览原始摘要信息 |
|
点击此处可从《Frontiers of Mathematics in China》下载全文 |