Book embeddings of regular graphs

József Balogh, Gelasio Salazar

Research output: Contribution to journalArticlepeer-review

Abstract

In the influential paper in which he proved that every graph with m edges can be embedded in a book with O(m1/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(m1/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(m1/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(m1/2) pages. We also give a simpler proof of Malitz's O(m1/2) bound and improve the proportionality constant.

Original languageEnglish (US)
Pages (from-to)811-822
Number of pages12
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number2
DOIs
StatePublished - Jan 1 2015

Keywords

  • Book embedding
  • Book thickness
  • Pagenumber
  • Stack number

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Book embeddings of regular graphs'. Together they form a unique fingerprint.

Cite this