BOOK EMBEDDINGS OF REGULAR GRAPHS

In the influential paper in which he proved that every graph with m edges can be embedded in a book with O(m(1/2)) pages, Malitz proved the existence of d-regular n-vertex graphs that require Omega(root dn 1/2-1d) pages. In view of the O(m(1/2)) bound, this last bound is tight when d > log n, and Malitz asked if it is also tight when d < log n. We answer negatively to this question by showing that there exist d-regular graphs that require Omega(n(1/2-1/2(d-1))) pages. In addition, we show that the bound O(m(1/2)) is not tight either for most d-regular graphs by proving that for each fixed d, with high probability the random d-regular graph can be embedded in o(m(1/2)) pages. We also give a simpler proof of Malitz's O(m(1/2)) bound and improve the proportionality constant.