我们研究以下距离实现问题：给定一个度量 $D$ 在一组终端 $T$ 上，是否存在一个（边加权的）外平面图 $G$，使得 $T \subseteq V(G)$，并且对于每一对 $t,t' \in T$，都有 $\mathrm{dist}_G(t,t')=D(t,t')$？我们首先证明不存在 "局部特征"，这与树和 Okamura-Seymour 实例形成对比。
我们的主要结果是一个高效的算法，其运行时间在 $|T|$ 上是多项式的。我们的证明和算法都利用了一种新的图结构分析方法，通过将图视为路径及其交叉点，这种方法我们认为具有独立的兴趣。
博主点评： 本文提出的高效算法在处理外平面图的度量问题上具有重要意义，尤其是通过路径和交叉点的视角进行分析，可能为图论研究带来新的思路。