Paths and Intersections: Recognizing Outerplanar Metrics
For researchers in metric embeddings and graph theory, it resolves a fundamental problem for outerplanar graphs, though the result is incremental given prior work on trees and Okamura-Seymour instances.
The paper solves the distance realization problem for outerplanar metrics, proving that no local characterization exists and providing a polynomial-time algorithm in the number of terminals.
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$, $\textsf{dist}_G(t,t')=D(t,t')$? 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 $|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.