| 平面图书式嵌入综述 |
| |
| 引用本文： | 关夏夏,吴楚雄,杨卫华,孟吉翔.平面图书式嵌入综述[J].数学进展,2020(1):1-12. |
| |
| 作者姓名： | 关夏夏 吴楚雄 杨卫华 孟吉翔 |
| |
| 作者单位： | 太原理工大学数学学院;新疆大学数学与系统科学学院 |
| |
| 基金项目： | 国家自然科学基金(No.11671296). |
| |
| 摘 要： | 图书式嵌入问题主要起源于大型集成电路(VLSI)设计和多层线路板印刷(PCBs)设计等诸多领域,有广泛的应用价值.图的书式嵌入是将图的点集排在一条直线上(书脊)且将边嵌入到以书脊为边界的半平面上(页)使得同页中的边互不相交.其研究的一个重要参数是页数(满足条件所需的最小页数),该问题是NP-困难的.本文主要综述平面图书式嵌入问题的相关研究.
|
| 关 键 词： | 书式嵌入 平面图 页数 |
A Survey on Book-embedding of Planar Graphs |
| |
| GUAN Xiaxia,WU Chuxiong,YANG Weihua,MENG Jixiang.A Survey on Book-embedding of Planar Graphs[J].Advances in Mathematics,2020(1):1-12. |
| |
| Authors: | GUAN Xiaxia WU Chuxiong YANG Weihua MENG Jixiang |
| |
| Institution: | (College of Mathematics,Taiyuan University of Technology,Taiyuan,Shanxi,030024,P.R.China;College of Mathematics and System Science,Xinjiang University,Urumqi,Xinjiang,830046,P.R.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 |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
