Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1

摘要

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 less than or equal to i < r, 0 less than or equal to 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 grill EM(r, s) is the graph whose vertex set is the set of pairs on nonnegative integers, {(i, j): 0 less than or equal to i < r, 0 less than or equal to j < s}, in which there is an edge between vertices (i, j) and (k, l) if and only if i - k less than or equal to 1 and j - l less than or equal to 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) less than or equal to 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. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 12]