EMBEDDINGS OF COMPLETE BINARY TREES INTO EXTENDED GRIDS WITH EDGE-CONGESTION 1∗
Marie-Claude Heydemann, Dominique Sotteau, Jaroslav Opatrný · International Journal of Parallel Emergent and Distributed Systems · 1996
Let G and H be two simple, undirected graphs. An embedding of the graph G into the graph H is an injective mapping f from the vertices of G to the vertices of H, together with a mapping which assigns to each edge [u, v] of G a path between f (u) and f (v) in H. The extended grid EM(r, s) is the graph whose vertex set is the set of pairs on nonnegative integers, {(i, j) : 0 ≤ i < r, 0 ≤ j < s}, in which there is an edge between vertices (i, j) and (k, l) if and only if |I – k| ≤ 1 and |j-l| ≤ 1. In this paper, we give an embedding of any complete binary tree of odd height into its optimal square extended grid. This embedding has edge-congestion 1, dilation 2 n-2 + 1, and its average dilation is less than 1.12. We also show that an embedding of a complete binary tree of odd height into its optimal grid, which is obtained from the embedding into the optimal extended grid by a simple transformation, has edge-congestion 2, dilation 22 n-1, and it creates in the grid far fewer edges of congestion 2 than the embedding from [9],