Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1 - Opatrny, Jaroslav; Sotteau, Dominique (Discrete Applied Mathematics, 2000)
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 grid M(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 either |i-k|=1 and j=l or i=k and |j-l|=1. 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 embeddings of complete binary trees into square grids and extended grids with total vertex-congestion 1, i.e., for any vertex x of the extended grid we have load(x)+vertex-congestion(x)<=1. Depending on the parity of the height of the tree, the expansion of these embeddings is approaching 1.606 or 1.51 for grids, and 1.208 or 1.247 for extended grids.