𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Embedding Meshes on the Star Graph

✍ Scribed by S. Ranka; J.C. Wang; N. Yeh

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
362 KB
Volume
19
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

We develop algorithms for mapping (n)-dimensional meshes on a star graph of degree (n) with expansion 1 and dilation 3 . We show that an (n)-degree star graph can efficiently simulate an (n)-dimensional mesh. 1993 Academic Press, Inc.

πŸ“œ SIMILAR VOLUMES

Embeddings of Star Graphs into Optical M
Embeddings of Star Graphs into Optical Meshes without Bends
✍ Stefan Thomas Obenaus; Ted H. Szymanski πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 377 KB

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 mes

On-line Planar Graph Embedding
On-line Planar Graph Embedding
✍ Roberto Tamassia πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 504 KB

We present a dynamic data structure for the incremental construction of a planar embedding of a planar graph. The data structure supports the following Ε½ . operations: i testing if a new edge can be added to the embedding without Ε½ . introducing crossing; and ii adding vertices and edges. The time c

The Order Upper Bound on Parity Embeddin
The Order Upper Bound on Parity Embedding of a Graph
✍ Thomas Zaslavsky πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 398 KB

A graph 1 is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according to whether its length is even or odd. The parity demigenus of 1 is the minimum of 2&/(S) (where / is the Euler characteristic) over all surfaces S in which 1 can be parity embedde

On the embedding of graphs into graphs w
On the embedding of graphs into graphs with few eigenvalues
✍ Vu, Van H. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 726 KB

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic