The problem of simulating one scheme for the interconnection of nodes on another is important in parallel computing and is essentially graph-theoretic. The star graph of order n has n ! vertices corresponding to permutations of the set ( 1 ,..., n ) , where two vertices are joined by an edge if and only if the permutations differ by a simple transposition involving 1. Thus, each element has n - 1 neighbors. Efficient embeddings of hypercubes, trees, and other topologies into the star graph have been made, as have embeddings of tori. This technical research report, however, presents a well-balanced embedding from the point of view of all three cost parameters: dilation, expansion, and congestion.

The authors use elementary group and graph theory and include a lot of detail, presented in a mathematical style. The paper is well illustrated and builds up to the torus embedding from a clear but technical discussion of cycle embedding. The interesting part is the proofs of cost control with, for instance, most of the dilation at one and at a maximum of four. It is possible that the proofs could be shortened by using more group theory. The result is usable in a theoretical sense, although any given case corresponding to a real design is likely to benefit from individual treatment. There are a few misprints and grammatical errors. The references are solid, and the paper’s layout makes it easy to follow.