Note: 

(LaTeX) Abstract: 
An embedding of the graph G in the graph H is a onetoone 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 expansioncost 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 nnode complete ternary trees in complete binary trees with dilationcost 2 and expansion cost O(n~), where ~ = 1og3(4/3); but any embedding of these ternary trees in binary trees that has expansioncost c < 2 must have dilationcost G(logloglogn). The second result provides a stronger but less easily stated example of the same type of tradeoff. The third result concerns generic binary trees, that is, complete binary trees into which all nnode binary trees are "efficiently" embeddable. There is a generic binary tree into which all nnode binary trees are embeddable with dilauoncost O(1) and expansioncost O(n ~) for some fixed constant c; if one insists on embeddings whose dilationcost is exactly 1, then these embeddings must have expansioncost f~(n¢~°*~)/~); tf one insists on embeddmgs whose expansioncost 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 threepart 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 contextfree grammars. 
URL for the Abstract: 

Categories,
Keywords: 
Categories and Subject Descriptors: F.I.2 [Computation by Abstract Devices]: Modes of Computation alternation and nondeterminism, F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerieal Algorithms and Problemscomputations on discrete structures, F.2.3 [Analysis of Algolithms and Problem Complexity]: Tradeoffs among Complexity Measures, G.2 2 [Discrete Mathematics]: Graph Theory General Terms: Algorithms, Theory
Additional Key Words and Phrases: Graph embeddings, dilationcost, expansioncost, cost tradeoffs, generic graphs 
HyperLinks / References / URLs: 
http://portal.acm.org/citation.cfm?doid=2157.322401 
Copyright Message: 

Personal Comments: 

Download
Access Level: 
Public 
