Speaker: Mohammad Taghi Hajiaghayi

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Plane embeddings of planar graph metrics

Abstract:

Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is
relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and
molecular reconstruction, we consider the natural problem of embedding shortest- path metrics
of unweighted planar graphs (planar graph metrics) into the Euclidean plane. It is known that,
in the special case of shortestpath metrics of trees, embedding into the plane requires(pn)
distortion in the worst case [19, 1], and surprisingly, this worst-case upper bound provides
the best known approximation algorithm for minimizing distortion. We answer an open question
posed in this work by proving that some planar graph metrics require (n2/3) distortion in any
embedding into the plane, proving the first separation between these two types of graph
metrics. We also prove that some planar graph metrics require (n) distortion in any
crossing-free straight-line embedding into the plane, suggesting a separation between
low-distortion plane embedding and the well-studied notion of crossing-free straight- line
planar drawings. Finally, on the upper-bound side, we prove that all outerplanar graph metrics
can be embedded into the plane with O(pn) distortion, generalizing the previous results on
trees (both the worst-case bound and the approximation algorithm) and building techniques for
handling cycles in plane embeddings of graph metrics.