Technical Report CS0547

This paper addresses a generalization of the book embedding problem, called the black/white (blw) book embedding problem, where a vertex-neighborhood constraint is imposed on the ordering of the vertices. A blw graph isa pair(G ,V), where G=(V,E) is a graph and U contained-in V is a set of distinguished black venices (the vertices in V-U are called white). A blw book embedding of (G ,V) is a book embedding of G, where the black vertices are arranged consecutively along the spine. Given a b/w graph (G ,V), the blw book embedding problem is that of finding a b/w book embedding of (G ,V), such that number of pages is minimized. The need for b/w embeddings may arise, for example, in applications where the input ports of a VLSI chip arc to be separated from the output ports.

The main resu1t of this paper is a characterization of the b/w graphs that admit a one-page b/w embedding. The characterization is given in tenns of a set of forbidden blw subgraphs, the absence of which is necessary and sufficient for one-page b/w embedding. For a b/w graph with non~ of these forbidden subgraphs, a one-page b/w embedding is constructible in linear tUne. The construction utilizes a technique called blw unfolding, which is a feature of independent interest

Key words: book embedding, outerplanar graphs, algorithm.