# zbMATH — the first resource for mathematics

Cost trade-offs in graph embeddings, with applications. (English) Zbl 0627.68038
An embedding of the graph G in the graph H is a one-to-one association of the vertices of G with the vertices of H. There are two natural measures of the cost of a graph embedding, namely, the dilation-cost of the embedding: the maximum distance in H between the images of vertices that are adjacent in G; and the expansion-cost of the embedding: the ratio of the size of H to the size of G. The main results of this paper illustrate three situations wherein one of these costs can be minimized only at the expense of a dramatic increase in the other cost. The first result establishes the following: There is an embedding of n-node complete ternary trees in complete binary trees with dilation-cost 2 and expansion cost $$\theta (n^{\lambda})$$, where $$\lambda =\log_ 3(4/3)$$; but any embedding of these ternary trees in binary trees that has expansion-cost $$c<2$$ must have dilation-cost $$\Omega$$ (log log log$${}_ n)$$. The second result provides a stronger but less easily stated example of the same type of trade-off. The third result concerns generic binary trees, that is, complete binary trees into which all n-node binary trees are “efficiently” embeddable. There is a generic binary tree into which all n-node binary trees are embeddable with dilation-cost O(1) and expansion- cost $$O(n^ c)$$ for some fixed constant c; if one insists on embeddings whose dilation-cost is exactly 1, then these embeddings must have expansion-cost $$\Omega (n^{(\log n)/2)})$$; if one insists on embeddings whose expansion-cost is less than 2, then these embeddings must have dilation cost $$\Omega$$ (log log log n). An interesting application of the polynomial size generic binary tree in the first part of this three-part result is to yield simplified proofs of several results concerning computational systems with an intrinsic notion of “computation tree”, such as alternating and nondeterministic Turing machines and context-free grammars.

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science
Full Text: