In this paper, we present a scheme for efficient embedding of torus of any dimension on a star graph. The dilation of the embedding is four. The expansion is small. Congestion depends upon the routing scheme used. With one routing scheme, the congestion is bound by a small constant (/spl ap/2) with an increase in expansion cost. For a second routing scheme, the congestion is O(n), for an n-star, with bounded expansion.

In this paper we present a scheme for congestion-free embedding of full binary trees on a star graph. The height of the tree that can be embedded with this scheme in an n-star is (n+1)[log/sub 2/n]-2/sup [log2n]+1/+1. The dilation of the embedding is two. This is an improvement by a factor of two over an earlier result.

A node ranking scheme provides the necessary structural view for developing algorithms on a network. We present two ranking schemes for the star interconnection network both of which allow constant time order preserving communication. The first scheme is based on a hierarchical view of the star network. It enables one to efficiently implement order preserving ASCEND/DESCEND class of algorithms. This class includes several important algorithms such as the Fast Fourier Transform (FFT) and matrix multiplication. The other ranking scheme gives a flexible pipelined view of the star interconnection network and provides a suitable framework for implementation of pipelined algorithms.