Embedding k-Outerplanar Graphs into lsub1

Motivated by the conjecture [17,19] that all metrics induced by planar graphs can be embedded into lsub1 with constant distortion, we study the class of k-outerplanar graphs [4]. We show that any metric induced by a k-outerplanar graph, for any fixed k, can be approximated by a probability distribution over tree metrics with constant distortion, and hence also embedded into lsub1 with constant distortion.