Cost trade-offs in graph embeddings, with applications.

*(English)*Zbl 0627.68038An 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 |