Embeddings of Star Graphs into Optical Meshes without Bends

✍ Scribed by Stefan Thomas Obenaus; Ted H. Szymanski

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 377 KB
• Volume: 44
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1356

✦ Synopsis

We show an embedding of the star graph into a rectangular optical multichannel mesh of d dimensions 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 an n-star, the mesh can have any number of dimensions d between 1 and n-1. The embedding has load 1 and an expansion of at most n 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 even n, the mesh will be no larger than n× 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 than n × n for even n with a load of (n -2)!.