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'\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.
From: Yu Chen [view email]
[v1]
Wed, 24 Jun 2026 13:45:01 UTC (1,765 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。