Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore.

Additionally, libraries can receive an extra 5% discount. Learn More

Additionally, libraries can receive an extra 5% discount. Learn More

Li Xianglu (Zhongyuan University of Technology, China)

Source Title: Modeling, Analysis, and Applications in Metaheuristic Computing: Advancements and Trends

Copyright: © 2012
|Pages: 7
DOI: 10.4018/978-1-4666-0270-0.ch018

Chapter Preview

TopThe book-embedding problem for graph *G* is to embed its vertices onto a line along the spine of the book and to draw the edges on pages of the book such that no two edges on the same page cross, and the number of used pages is minimized.

The book-embedding problem has been motivated by several areas of computer science such as VLSL theory, multilayer printed circuit boards (PCB), sorting with parallel stacks and Turning-machine and the design of fault-tolerant processor arrays, etc (e.g., Chung et al., 1987). The DIOGENES approach to fault-tolerant processor arrays, proposed by Rosenberg (1986), is the most famous one. In the DIOGENES approach, the processing elements are laid out in a logical line, and some number of bundles of wires run in parallel with the line. The faulty elements are bypassed, and the fault-free ones are interconnected through the bundles. Here, the bundles work as queues and/or stacks. If the bundles work as stacks, then the realization of an interconnection network needs a book-embedding of the interconnection network. In this case, the number of pages corresponds to the number of bundles of the DIOGENES stack layout. Therefore, book-embeddings with few pages realize more hardware-efficient DIOGENES stacks layouts.

The book-embedding problem can be stated as a graph-labeling problem as follows. We shall follow the graph-theoretic terminology and notation used by Bondy and Murty (1976) and Golumbic (1980).

Given a simple connected graph *G*=(*V*,*E*) with *n* vertices, a bijection *f*:is called a *labeling* of *G* by Chung(1988), where represents the label of vertex *v* ϵ *V*. Let be the vertex with label *i*. Then the labeling *f* can also be regarded as an ordering on a line. For a labeling *f*, two edges are said to be *crossing* if or .

With respect to a labeling *f*, a partition of the edge set *E*(*G*) is called a *page partition* if no two edges in any subset are crossing. This page partition can be thought of as a coloring of *E*(*G*) where the edges in *E _{i}* have color

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved