2018/01/22 by Guan, Xiaxia, Yang, Weihua
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1801.07097
A book-embedding of a graph G is an embedding of vertices of G along the spine of a book, and edges of G on the pages so that no two edges on the same page intersect. the minimum number of pages in which a graph can be embedded is called the page number. The book-embedding of graphs may be important in several technical applications, e.g., sorting with parallel stacks, fault-tolerant processor arrays design, and layout problems with application to very large scale integration (VLSI). Bernhart and Kainen firstly considered the book-embedding of the planar graph and conjectured that its page number can be made arbitrarily large [JCT, 1979, 320-331]. Heath [FOCS84] found that planar graphs admit a seven-page book embedding. Later, Yannakakis proved that four pages are necessary and sufficient for planar graphs in [STOC86]. Recently, Bekos et al. [STACS14] described an O(n2) time algorithm of two-page book embedding for 4-planar graphs. In this paper, we embed 5-planar graphs into a book of three pages by an O(n2) time algorithm.