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 Ω( √ dn 1/2-1/d ) 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 Ω(n 12-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.