2-PAGE BOOK EMBEDDING OF TREES UNDER VERTEX-NEIGHBORHOOD CONSTRAINTS

We study the VLSI-related problem of embedding graphs in books. A book embedding of a graph G=(V,E) consists of two parts, namely, (1) an or dering of V along the spine of the book, and (2) an assignment of each e is-an-element-of E to a page of the book, so that edges assigned to the same page do not intersect. In devising an embedding, one seeks t o minimize the number of pages used. A black/white (b/w) graph is a pa ir (G, U), where G is a graph and U subset-or-equal-to V is a subset o f distinguished black vertices (the vertices of V- U are called white) . A black/white (b/w) book embedding of a b/w graph (G, U) is a book e mbedding of G, where the vertices of U are placed consecutively on the spine. The need for b/w embeddings may arise, for example, when the i nput ports of a multilayer VLSI chip are to be separated from the outp ut ports. 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, w hich uses an extension of the unfolding technique introduced by Moran and Wolfsthal. Combining this algorithm with the one of Moran and Wolf sthal results in a linear time algorithm for optimal b/w embedding of trees.