Minimum Congestion Embedding of Complete Binary Trees into Tori

Akira MATSUBAYASHI  Ryo TAKASU  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.9   pp.1804-1808
Publication Date: 2000/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
graph embedding,  congestion,  complete binary tree,  torus,  

Full Text: PDF(952.7KB)>>
Buy this Article




Summary: 
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 2n-1-vertex complete binary tree can be embedded in a (2n/2+1)(2n/2+1)-grid and a 2n/2 2n/2-grid with congestion 1 and 2, respectively. However, it is not known if 2n-1-vertex complete binary tree is embeddable in a 2n/2 2n/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 2n/2 2n/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.