## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 811-822 |

Number of pages | 12 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 29 |

Issue number | 2 |

DOIs | |

State | Published - Jan 1 2015 |

## Keywords

- Book embedding
- Book thickness
- Pagenumber
- Stack number

## ASJC Scopus subject areas

- Mathematics(all)