### The pagenumber of genus $\textit{g}$ graphs is $O(\textit{g})$The pagenumber of genus $\textit{g}$ graphs is $O(\textit{g})$

Access Restriction
Subscribed

 Author Heath, Lenwood S. ♦ Istrail, Sorin Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1992 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Book embeddings ♦ Graph genus ♦ Homotopy classes ♦ Planar-nonplanar decomposition ♦ Surface embeddings Abstract In 1979, Bernhart and Kainen conjectured that graphs of fixed genus $\textit{g}$ ≥ 1 have unbounded pagenumber. In this paper, it is proven that genus $\textit{g}$ graphs can be embedded in $\textit{O}(\textit{g})$ pages, thus disproving the conjecture. An $&OHgr;(\textit{g}1/2)$ lower bound is also derived. 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 is presented. First, the algorithm computes the genus $\textit{g}$ of a graph using the algorithm of Filotti, Miller, Reif (1979), which is polynomial-time for fixed genus. Second, it applies an optimal-time algorithm for obtaining an $\textit{O}(\textit{g})-page$ book embedding. Separate book embedding algorithms are given for the cases of graphs embedded in orientable and nonorientable surfaces. An important aspect of the 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 obtained: fault-tolerant VLSI and complexity theory. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1992-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 39 Issue Number 3 Page Count 23 Starting Page 479 Ending Page 501

#### Open content in new tab

Source: ACM Digital Library