We study the VLSI-related problem of embedding graphs in books. A blacklwhite (b/w) book embedding of a b/w graph (G,U) is a book embedding of G, where the vertices of U are placed consecutively on the spine. In this paper we prove that every b/w tree admits a two-page b/w embedding. The proof takes the form of a linear time algorithm, which uses an extension of the unfolding technique.
展开▼
