The page number of genus g graphs is (g)
Lenwood S. Heath, Sorin Istrail · 1987
This paper disproves the conjecture that graphs of fixed genus g ≤ 1 have unbounded pagenumber (Bernhart and Kainen, 1979). We show that genus g graphs can be embedded in Ο(g) pages, and derive an Ω(√g) lower bound. We present the first algorithm in the literature for embedding an arbitrary graph in a book with a non-trivial upper bound on the number of pages. We first compute the genus g of a graph using the algorithm of Filotti, Miller, Reif (1979), and then apply our (optimal-time) algorithm for obtaining an Ο(g) page embedding. An important aspect of our construction is a new decomposition theorem, of independent interest, for a graph embedded on a surface. Book embedding has application in several areas, two of which are directly related to the results we obtain: fault-tolerant VLSI and complexity theory.