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' \in T$, we have $\mathrm{dist}_G(t,t')=D(t,t')$? We first prove that there is no "local characterization," contrasting with trees and Okamura-Seymour instances.
Our main result is an efficient algorithm for this problem whose running time is polynomial in $|T|$. 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.
Blogger's Review: The efficient algorithm presented in this paper is significant for addressing the metric problem of outerplanar graphs, particularly through the perspective of analyzing paths and intersections, which may bring new insights into graph theory research.