Peeling Half the Onion: Embedding $k$-Outerplanar Graphs into ${\ell }_1$ and Trees with a Polynomial Distortion (in $k$)

Hsien-Chih Chang, Jonathan Conroy, William Eliot +2

Chekuri, Gupta, Newman, Rabinovich, and Sinclair [SODA'03] showed that $k$-outerplanar graphs can be embedded into trees and ${\ell }_1$ with distortion $2^{O(k)}$. Their result is pe…