A survey on book-embedding of planar graphs

作     者：Xiaxia GUAN Chuxiong WU Weihua YANG Jixiang MENG Xiaxia GUAN;Chuxiong WU;Weihua YANG;Jixiang MENG

作者机构：College of MathematicsTaiyuan University of TechnologyTaiyuan 030024China College of Mathematics and System ScienceXinjiang UniversityUrumqi 830046China 

出 版 物：《Frontiers of Mathematics in China》 (中国高等学校学术文摘·数学（英文）)

年 卷 期：2022年第17卷第2期

页      面：255-273页

核心收录：

学科分类：07[理学] 0701[理学-数学] 

主　　题：Book embedding planar graphs pagenumber 

摘      要：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.