Technical Report CS0547

Title: One-Page Book Embedding Under Vertex Neighborhood Constraints
Authors: S. Moran and Y. Wo1fstah1
Abstract: 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 ordering of V along the spine of the book, and (2) an assignment of each e from E to a page of the book, so that edges assigned to the same page do not intersect. In devising an-embedding, one seeks to minimize the number of pages used.

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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion