平面图书式嵌入综述

A Survey on Book-embedding of Planar Graphs

图书式嵌入问题主要起源于大型集成电路(VLSI)设计和多层线路板印刷(PCBs)设计等诸多领域,有广泛的应用价值.图的书式嵌入是将图的点集排在一条直线上(书脊)且将边嵌入到以书脊为边界的半平面上(页)使得同页中的边互不相交.其研究的一个重要参数是页数(满足条件所需的最小页数),该问题是NP-困难的.本文主要综述平面图书式嵌入问题的相关研究.

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.