This book is the first volume in the Foundations of Computing Series edited by Michael R. Garey. The contexts of this book are, for the most part, drawn from the PhD thesis by Leighton. Having read it with much enthusiasm, I highly recommend it to all those who are interested in the fundamental issues involved in the theory of VLSI layout. The author introduces an abundance of new ideas and techniques in a most-motivating and well-written manner. Moreover, these techniques and the given proofs are both powerful and elegant and show the author’s inventiveness and deep insight into the subject matter.

The book consists of two main parts, each divided into four chapters. The first part is an indepth study of layouts for the Shuffle-Exchange Graph (SEG). The layout is according to Thompson’s grid model [1]. The main objectives of the layout are to minimize the layout area, the crossing number, and the maximum edge length. The SEG is partitioned into necklaces (which are disjoint simple cycles) and shuffle edges (that cannect two nods in different necklaces). Hoey and Leiserson’s Complex-Plane Diagram [2] is used as a tool to assist the layout process. The layout stats with a level-necklace grid in which the nodes and the edges of the necklaces are first laid out so that each necklace occupies two or three adacent rows and columns will be used. The key points in such a layout are: “In hat order should the necklaces be assigned to columns?” and “What row should each node be assigned to?” For the first point, various heuristics, such as order by size, radius, or minimum value, are discussed. The author points out that the best ordering of necklaces remains an open problem. However, by a clever use of this layout idea, a layout that achieves the optimum area and crossing number simultaneously to within a constant factor is obtained. Several other layouts are given, some of them being suboptimal but practical layouts. The results of the first part, for the N-node SEG, may be summarized as follows: Layout area is &thgr; (N²/log²N), crossing number &thgr; (N²/log²N), maximum edge length is between O(N/logN) and &OHgr; (n/log²N). As motivated by the second part of the book, the author poses the open question that whether the SEG has an O(N/logN) separator.

The second part deveops a number of layout lower bound techniques. For several networks, such as the r-dimensional mesh of trees, r :3W 2, the tree of meshes, and the augmented tree of meshes are considered. It is shown that the N-node 2-dimensional mesh of the trees is the first know graph with an O (N^1/2)-separator to achieve tight bounds of &thgr; (N logN) crossing number, and &thgr; (N^1/2 logN/loglogN) maximum edge length. The rdimensional mesh of trees, for r :3W 3, is the first known graph with an O (NN^{:G a})-separator, :G a :-3J 1/2, to have tight bound of &thgr; (N^&agr;) for the maximum edge length. For the latter graph the layout area and the crossing number are &thgr; (N² ).

The N-node tree of meshes is shown to be the first planar graph to require &thgr; (NlogN) layout area. This disproves the conjecture that any planar graph has a linear layout area. The augmented tree of meshes least :G o (N/logN^1/2) maximum edge length.

It is also shown that the mesh of trees is a powerful parallel computer that can perform computations such as sorting, switching, matrix-vector multiplication in logarithic number of steps. Unlike the SEG, the mesh of trees and the tree of meshes are easy to lay out on a chip. The hard part is to prove that their layouts are optimal. To accomplish this task, a new reduction technique is used in proving lower bound on layout area, crossing number, and maximum edge length. The technique is a generalized embedding that can be described as follows: Embed a graph G₁ into a graph G_2:, and each edge of G₁ is embedded on a particular path of G₂ between the corresponding nodes. In this way, it is shown, that having a layout lower bound for G₁, we can obtain a layout lower bound for G₂. This idea turns out to be very powerful and many results are drawn from it. In particular, the crossing number of K_N into it. The author also shows how to embed a 2-dimensional mesh of trees into the tree of meshes to obtain lower bounds for the latter graph.

Some general results are also proven. For instance, for any graph we have :G O (B ₂) :3W C + N :3W O (A), where B = bisection width, = crossing number, W = wire area, A = layout area. It is then shown that any network which computes in N-variable transitive function (such as sorting or discrete Fourier transform) in time T = o(N_1/2) must have C wire crossings where CT₂ :G O (N₂). This crossing-time tradeoff is a generalization of Thompson’s area-time tradeoff (see [1]). Some applications of this new tradeoff are discussed. The book also contains an addendum that points out recent related work done after the first draft of this book. Many references to important papers are given.