Access Restriction

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

   Open content in new tab
Source: ACM Digital Library