Hypercube

• (n-1) coordinate plus one more dimension
• Could be used in parallel processing, with vertices as processors, and edges connecting them
• Construction
  • Make a copy of the d-dim hypercube, from c to c'
  • Connect the corresponding vertices in c and c' by edges.
• Deriving the number of edges:

$$\{\begin{array}{l}E(n)=2E\left(\frac{n}{2}\right)+\frac{n}{2}\\ E(2)=1\end{array}\Rightarrow E(n)=O(n\log n)$$

• Distance between nodes is $O(\log n)$, by jumping to the same sub-cube on and on.
• Meanwhile, the mesh structure
  • Has a fixed degree (4)
  • Distance between nodes can be $\sqrt{n}$
  • Cutting the mesh horizontally and vertically into 4 sub-meshes

$$\{\begin{array}{l}{E}_m(n)=4E_m\left(\frac{n}{4}\right)+2\sqrt{n}\\ E(1)=0\end{array}$$

• Complete binary-tree (cutting from the root into 2 sub-trees)

$$\{\begin{array}{l}{E}_T(n)=2E_T\left(\frac{n-1}{2}\right)+2\\ E_T(1)=0\end{array}$$