Genus g graphs have pagenumber O(√g)

A book embedding of a graph consists of a linear ordering of the vertices along the spine of a book and an assignment of edges to pages so that edges on the same page do not intersect. The minimum number of pages in which a graph can be embedded is its pagenumber. The following results are presented: (1) any graph of genus g has pagenumber O(√g); and (2) most n-vertex d-regular graphs have pagenumber Ω(√dn^1/2-1d/)