%T Combinatorial Theorems about Embedding Trees on the Real Line
%A Amit Chakrabarti
%A Subhash Khot
%R Technical Report TR2005-560
%I Dartmouth College, Computer Science
%C Hanover, NH
%D October 2005
%U http://www.cs.dartmouth.edu/reports/TR2005-560.pdf
%X
 We consider the combinatorial problem of embedding a tree metric into
 the real line with low distortion. For two special families of trees ---
 the family of complete binary trees and the family of subdivided stars
 --- we provide embeddings whose distortion is provably optimal, up to a
 constant factor. We also prove that the optimal distortion of a linear
 embedding of a tree can be arbitrarily low or high even when it has
 bounded degree.