Embeddings of complete binary trees into extended grids with edge-congestion 1 - Heydemann, Marie-Claude; Sotteau, Dominique; Opatrny, Jaroslav (Parallel Algorithms and Applications, 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 2^(n-1), and it creates in the grid far fewer edges of congestion 2 than the embedding from Zienicke (1990).