Paths and Intersections: Recognizing Outerplanar Metrics

We study the following distance realization problem: given a metric $D$ on a set $T$ of terminals, does there exist an (edge-weighted) outerplanar graph $G$, such that $T\subseteq V(G)$, and for every pair $t,t^{\mathrm{\prime }}\in T$, ${\mathsf{\text{dist}}}_G(t,t^{\mathrm{\prime }})=D(t,t^{\mathrm{\prime }})$? We first prove that there is no ``local characterization’', forming a contrast with trees and Okamura-Seymour instances. Our main result is an efficient algorithm for this problem whose running time is polynomial in $\mathrm{\mid }T\mathrm{\mid }$. Both our proof and our algorithm utilize a recent new approach of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.