The book embedding of a graph G consists of placing the vertices of G in a line called spine and assigning edges of the graph to pages so that the edges assigned to the same page do not intersect. The number of pages ...The book embedding of a graph G consists of placing the vertices of G in a line called spine and assigning edges of the graph to pages so that the edges assigned to the same page do not intersect. The number of pages is the minimum number in which the graph can be embedded. In this paper, we study the book embedding of the Cartesian product Pm × Sn, Pm × Wn, Cn × Sm, Cn × Wm, and get an upper bound of their pagenumber.展开更多
A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the qual...A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph G can be embedded. In this paper, the authors discuss the embedding of the generalized Petersen graph and determine that the page number of the generalized Petersen graph is three in some situations, which is best possible.展开更多
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 em...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.展开更多
A book embedding of a graph G is a placement of its vertices along the spine of a book,and an assignment of its edges to the pages such that no two edges on the same page cross.The pagenumber of a graph is the minimum...A book embedding of a graph G is a placement of its vertices along the spine of a book,and an assignment of its edges to the pages such that no two edges on the same page cross.The pagenumber of a graph is the minimum number of pages in which it can be embedded.Determining the pagenumber of a graph is NP-hard.A graph is said to be 1-planar if it can be drawn in the plane so that each edge is crossed at most once.The anthors prove that the pagenumber of 1-planar graphs is at most 10.展开更多
基金The NSF(A2015202301)HUSTP(ZD201506)RFHED(QN2016044)of Hebei Province
文摘The book embedding of a graph G consists of placing the vertices of G in a line called spine and assigning edges of the graph to pages so that the edges assigned to the same page do not intersect. The number of pages is the minimum number in which the graph can be embedded. In this paper, we study the book embedding of the Cartesian product Pm × Sn, Pm × Wn, Cn × Sm, Cn × Wm, and get an upper bound of their pagenumber.
基金supported by the National Natural Science Foundation of China(Nos.11531010,11401510,11501487)the Key Laboratory Project of Xinjiang(No.2015KL019)the Doctoral Fund of Xinjiang University(No.BS150208)
文摘A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a measure of the quality of a book embedding which is the minimum number of pages in which the graph G can be embedded. In this paper, the authors discuss the embedding of the generalized Petersen graph and determine that the page number of the generalized Petersen graph is three in some situations, which is best possible.
文摘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.
基金supported by the National Natural Science Foundation of China(Nos.12371356,12401462)the Natural Science Foundation of Shanxi Province(No.20210302123097).
文摘A book embedding of a graph G is a placement of its vertices along the spine of a book,and an assignment of its edges to the pages such that no two edges on the same page cross.The pagenumber of a graph is the minimum number of pages in which it can be embedded.Determining the pagenumber of a graph is NP-hard.A graph is said to be 1-planar if it can be drawn in the plane so that each edge is crossed at most once.The anthors prove that the pagenumber of 1-planar graphs is at most 10.
