Minimum congestion embedding of complete binary trees into tori
We consider the problem of embedding complete binary trees into 2-dimensional tori with minimum (edge) congestion. It is known that for a positive integer n, a 2(n) - 1-vertex complete binary tree can be embedded in a (2 ([n/2]) + 1) x (2 ([n/2]) + 1)-grid and a 2 ([n/2]) x 2 ([n/2])-grid with congestion 1 and 2, respectively. However, it is not known if 2n - 1-vertex complete binary tree is embeddable in a 2([n/2]) X 2([n/2])-grid with unit congestion. In this paper, we show that a positive answer can be obtained by adding wrap-around edges to grids, i.e., a 2n - 1-vertex complete binary tree can be embedded with unit congestion in a 2([n/2]) X 2([n/2])-torus. The embedding proposed here achieves the minimum congestion and an almost minimum size of a torus (up to the constant term of 1). In particular, the embedding is optimal for the problem of embedding a 2n - 1-vertex complete binary tree with an even integer n into a square torus with unit congestion.
congestion complete binary tree torus graph embedding