Combinatorial theorems about embedding trees on the real line

Amit Chakrabarti, Subhash Khot

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the combinatorial problem of embedding the metric defined by an unweighted graph into the real line, so as to minimize the distortion of the embedding. This problem is inspired by connections to Banach space theory and to computer science. After establishing a framework in which to study line embeddings, we focus on metrics defined by three specific families of trees: complete binary trees, fans, and combs. We construct asymptotically optimal (i.e., distortion-minimizing) line embeddings for these metrics and prove their optimality via suitable lower bound arguments. It appears that even such specialized metrics require nontrivial constructions and proofs of optimality require sophisticated combinatorial arguments. The combinatorial techniques from our work might prove useful in further algorithmic research on low distortion metric embeddings.

Original languageEnglish (US)
Pages (from-to)153-168
Number of pages16
JournalJournal of Graph Theory
Volume67
Issue number2
DOIs
StatePublished - Jun 2011

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint Dive into the research topics of 'Combinatorial theorems about embedding trees on the real line'. Together they form a unique fingerprint.

Cite this