English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Cost Trade-offs in Graph Embeddings, with Applications

MPS-Authors

Hong,  Jia-Wei
Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Rosenberg,  Arnold L.
Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Hong, J.-W., Mehlhorn, K., & Rosenberg, A. L. (1983). Cost Trade-offs in Graph Embeddings, with Applications. Journal of the ACM, 30(4), 709-728. doi:10.1145/2157.322401.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-AF2F-7
Abstract
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 dilationcost 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 situaUons 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 O(n~), where ~ = 1og3(4/3); but any embedding of these
ternary trees in binary trees that has expansion-cost c < 2 must have
dilation-cost G(logloglogn). 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 dilauon-cost O(1) and
expansion-cost O(n ~) for some fixed constant c; if one insists on embeddings
whose dilation-cost is exactly 1, then these embeddings must have
expansion-cost f~(n¢~°*~)/~); tf one insists on embeddmgs whose expansion-cost
is less than 2, then these embeddings must have dilation cost ~(log log log n)
An interesting application of the polynomial size genenc binary tree m the
first part of this three-part result is to yield simplified proofs of several
results concerning computational systems with an intrinsic nouon of
"computation tree," such as alternating and nondeterministic Turing machines
and context-free grammars.