{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T02:02:41Z","timestamp":1787364161486,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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(\\sqrt{d}n^{\\frac{1}{2}-\\frac{1}{d}})$ pages. In view of the $O({m}^{1\/2})$ bound, this last bound is tight when $d &gt; \\log{n}$, and Malitz asked if it is also tight when $d&lt; \\log{n}$. We answer negatively to this question by showing that there exist $d$-regular graphs that require $\\Omega(n^{\\frac{1}{2}-\\frac{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.<\/jats:p>","DOI":"10.1137\/140961183","type":"journal-article","created":{"date-parts":[[2015,4,21]],"date-time":"2015-04-21T12:07:06Z","timestamp":1429618026000},"page":"811-822","source":"Crossref","is-referenced-by-count":4,"title":["Book Embeddings of Regular Graphs"],"prefix":"10.1137","volume":"29","author":[{"given":"J\u00f3zsef","family":"Balogh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gelasio","family":"Salazar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,4,21]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90021-2"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.2307\/2317525"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/0608002"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.11.001"},{"key":"atypb5","first-page":"463","volume":"2","author":"Erdo\u0308s P.","year":"1935","journal-title":"Compos. Math."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00144-6"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1773"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146643"},{"key":"atypb9","first-page":"76","author":"Kainen P.C.","year":"1974","journal-title":"Berlin"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1027"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1028"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/100794651"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1969-12393-1"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1049"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.0.CO;2-S"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321704"},{"key":"atypb17","first-page":"239","author":"Wormald N.","year":"1999","journal-title":"Cambridge"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90032-9"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140961183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:24:53Z","timestamp":1787322293000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140961183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140961183"],"URL":"https:\/\/doi.org\/10.1137\/140961183","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}