Embeddings of complete binary trees into star graphs with congestion 1

Gives a construction of embeddings of vertex-congestion 1 and dilation 4 of complete binary trees into star graphs. The height of the trees embedded into the n-dimensional star graph S_n is (n+1)[log₂ n]-2^{[log n]+1}+1, which improves the previous result from Bouabdallah and Heydemann (1993, 1994) by more than n/2-1. We then construct embeddings of vertex-congestion 1, dilation at most (5n/4)+2, of complete binary trees into the n-dimensional star graph, whose height differs from the theoretical upper bound of log₂n! by less than 3[log₂n]. Our results show that the star networks can efficiently simulate algorithms that are intended for a binary tree architecture