EMBEDDING COMPLETE BINARY-TREES INTO STAR AND PANCAKE GRAPHS

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 t o the vertices of H. The dilation of the embedding is the maximum dist ance between f(u), f(v) taken over all edges (u, v) of G. We give a co nstruction of embeddings of dilation 1 of complete binary trees into s tar graphs. The height of the trees embedded with dilation 1 into the n-dimensional star graph is Omega (n log n), which is asymptotically o ptimal. Constructions of embeddings of complete binary trees of dilati on 2 delta and 2 delta + 1, delta greater than or equal to 1, into sta r graphs are given. The use of larger dilation allows embeddings of tr ees of greater height into star graphs. It is shown that all these con structions can be modified to yield embeddings of dilation 1 and 2 del ta, delta greater than or equal to 1, of complete binary trees into pa ncake graphs.