In a hypercube, e-cube routing (or dimension-order routing) routes a message
from source to destination by traversing the differing dimensions in
right-to-left order (or left-to-right: the specific order is irrelevant, as long
as all routers use the same ordering). Thus if a message is going from 11001
to 10010, the differing dimensions are shown by the xor, 01011, and so the e-cube
routing path would be 11001 to 11000 to 11010 to 10010.
Since e-cube routing is the routing typically supplied in commercial hypercubes,
for optimal performance a user would prefer to embed a task graph so that
different communication links between tasks are not mapped onto the same
physical link.
An *e-circuit embedding* of a task graph *G* into a hypercube
*Q* is a
1-1 mapping of the vertices of *G* into the vertices of *Q*, such
that when the edges of *G* are mapped to the paths that the e-cube
router would use to route between the two endpoints, no two
paths share a link.
All edges of the hypercube are viewed as being 2 links, one in
each direction.
Each edge of *G* is mapped to 2 different paths of the hypercube,
corresponding to the two directions of the edge.
Note that in any path with distance greater than 1, the e-cube
router uses different edges of the hypercube for the two directions.
**Theorem:**
Let *G=(V,E)* be a connected undirected graph.
Then *G* can be e-cube embedded into a hypercube if and only if there
is a labeling *L:E-> {1,2,...}* such that

- For every cycle
*C* of *G*, the smallest label that occurs
on *C* appears an even number of times.
- For every vertex
*v* of *G*, no two edges incident on *v*
have the same label.

Further, if *G* has *n* vertices and labels *{1,...,d}* are
used, then G can be embedded into a hypercube of dimension
*2d+2 ceiling(lg n)*
**Keywords:**
hypercube computer, graph embedding, e-cube routing,
dimension order, link contention, graph theory, computer science,
parallel computing, parallel computer architecture