Embeddings of Star Graphs into Optical Meshes without Bends

We show an embedding of the star graph into a rectangular optical multichannel mesh ofddimensions such that the embedding has no bends; that is, neighbors in the star graph always differ in exactly one coordinate in the mesh, to facilitate one-hop optical communication. To embed ann-star, the mesh can have any number of dimensionsdbetween 1 andn− 1. The embedding has load 1 and an expansion of at mostn^{d − 1}/d!. The size of the mesh will be at most We optimize the size of the host mesh using clique-partitioning to produce embeddings with expansions as low as unity. In two dimensions, for evenn, the mesh will be no larger thann×n(n− 2)!, and have an expansion of no more than 1 1/(n− 1). Further, we show how we can use a contraction method to efficiently embed the star graph into an optical mesh with near-unity aspect ratios. Contraction on a two-dimensional embedding will yield a mesh of size no larger thann×nfor evennwith a load of (n− 2)!.