{"id":"arxiv/2607.02883","url":"https://arxiv.org/abs/2607.02883","tags":["cs.DS","cs.CG","math.CO"],"score":0,"title":"Paths and Intersections: Repelling Pairs","domain":"cs.DS","source":"arxiv","authors":["Yu Chen","Pavlo Pylyavskyy","Zihan Tan"],"reviews":0,"subject":"cs.DS","summary":"We study two inverse problems for shortest-path metrics of Okamura-Seymour instances: recognizing metrics realizable by outerplanar graphs, and computing minimum-edge Okamura-Seymour realizations. We introduce the notion of \\emph{repelling pairs}, a metric certificate that the shortest paths corresponding to two terminal pairs must be vertex-disjoint in every realization. Our central structural result is that, for an Okamura-Seymour metric with a prescribed cyclic order, a terminal path structure in an Okamura-Seymour instance can be realized by nonnegative edge lengths if and only if the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-03","reactions":{}}