Paths and Intersections: Recognizing Outerplanar Metrics

Abstract

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^{\prime }\in T$, ${\text{dist}}_G(t,t^{\prime })=D(t,t^{\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 $|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.

arXiv commentThis paper has been merged into the most recent version of [arXiv:2607.02883]