Technical Report CS0552

TR#:CS0552
Class:CS
Title: Two-Page Book Embedding of Trees Under Vertex-Neighborhood Constraints
Authors: S. Moran and Y. Wolfstahl
PDFCS0552.pdf
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.

A black/white (blw) graph is a pair (G,U), where G is a graph and U in V is a subset of distinguished black vertices (the vertices of V-U are called white). A black/white (blw) book embedding of a blw graph (G ,U) is a book embedding 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 input ports of a multilayer VLSI chip are to be separated from the output 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, which uses an extension of the unfolding technique inttoduced in [MW]. Combining this algorithm with the one in [MW] results in a linear time algorithm for optimal b/w embedding of trees.

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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1989/CS/CS0552), 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
admin