Book embeddings of regular graphs Article uri icon

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%27s O(m1/2) bound and improve the proportionality constant. © 2015 Society for Industrial and Applied Mathematics. Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
  • 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. © 2015 Society for Industrial and Applied Mathematics. Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

publication date

  • 2015-01-01