Book-Embedding Of Planar Graphs

A book e'mbedding 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 so that no two edges on the same page cross.The book-embedding problem arises in several area,such as direct interconnection networks,VLSI design,fault-tolerant processor arrays,sorting with parallel stacks and so on.It can be used into various practical application fields.A graph is said to be planar if it can be drawn in the plane so that its edges do not cross.A planar graph of maximum degree k is called a planar k-graphA graph is said to be 1-planar if it can be drawn in the plane so that each edge is crossed at most once.In this paper,we mainly research book embeddings of planar 5-graphs and 1-planar graphs and obtain the two results as following.One is that we embed planar 5-graphs with n vertices into books of three pages by an O(n2)time algorithm similar to that of Bekos[M.A.Bekos,M.Gronemann,and C.N.Raftopoulou,Two-page book embeddings of 4-planar graphs,31st Symposium on Theoretical Aspects of Computer Science(2014)137-148].The other is that we embed 1-planar graphs into a book of thirteen pages by an liner time algorithm by improving the algorithm of Alam[M.J.Alam,F.Brandenburg,and S.Kobourov,On the Book Thickness of 1-Planar Graphs,arXiv:1510.05891].