Pith. sign in

REVIEW 4 minor 1 cited by

Outerplanar distance metrics have no constant-point characterization, yet can still be recognized in polynomial time by treating graphs as collections of paths and their intersections.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-12 12:10 UTC pith:LJ4TOGQY

load-bearing objection Solid poly-time recognition for outerplanar metrics plus a clean no-local-characterization result; the paths-and-intersections machinery is the real reusable piece.

arxiv 2606.25827 v2 pith:LJ4TOGQY submitted 2026-06-24 cs.DS

Paths and Intersections: Recognizing Outerplanar Metrics

Yu Chen , Zihan Tan This is my paper
classification cs.DS MSC 05C1268Q2590C05
keywords outerplanar graphsdistance realizationmetric embeddingshortest pathsOkamura–Seymourdynamic programmingpath intersections
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper asks when a finite metric on k labeled terminals can be realized exactly as shortest-path distances in some edge-weighted outerplanar graph. Unlike trees and Okamura–Seymour instances, which admit simple four-point conditions, outerplanar metrics have no O(1)-point characterization: for every k ≥ 20 there exist metrics that fail to be outerplanar while every proper restriction is outerplanar. Nevertheless the authors give a complete polynomial-time algorithm that decides the question and constructs a realizing graph whenever one exists, running in O(k^5) time. The algorithm first recovers a circular order of the terminals, then builds a canonical outerplanar skeleton together with a designated shortest-path structure that obeys a simple “repelling-paths” condition; a linear program then assigns edge lengths that make those paths shortest and of the prescribed lengths. Both the non-existence proof and the algorithm rest on the same conceptual move: treat the graph purely as a collection of paths and the combinatorial pattern of their intersections.

Core claim

A metric on k terminals is outerplanar if and only if there exists a canonical outerplanar graph and a shortest-path structure on its terminals such that every pair of repelling terminal pairs is assigned disjoint paths; the existence of such a structure can be decided by dynamic programming in O(k^5) time, after which a distance LP that is guaranteed feasible by a dual-flow argument recovers the edge weights.

What carries the argument

The repelling-paths condition: two pairs of terminals are repelling when their four distances violate one of the two inequalities that would be forced by intersecting shortest paths; the condition simply requires that every such pair of paths be placed disjointly. Sufficiency of the condition for the existence of edge lengths is proved by showing that any dual flow obstruction can be uncrossed until it contradicts the four-point properties of Okamura–Seymour metrics.

Load-bearing premise

Once a candidate collection of paths satisfies the combinatorial repelling condition, the associated linear program for edge lengths is always feasible; that claim rests on a pure combinatorial lemma equating chord dominance with the possibility of successive uncrossing.

What would settle it

Exhibit a concrete metric and a path structure that obeys every repelling-paths condition yet for which the dual flow LP still admits a positive-cost obstruction, or find a finite family of forbidden submetrics that completely characterises outerplanarity.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Any distance-realization problem whose graphs admit a circular order of terminals can be attacked by first recovering that order and then searching for a path structure that respects a suitable non-crossing condition.
  • The same path-intersection viewpoint yields a polynomial algorithm for outerplanar metrics even though no constant-point local certificate exists.
  • The dual-flow / uncrossing argument shows that numerical feasibility of edge lengths is completely determined by a combinatorial intersection pattern.
  • Canonical outerplanar skeletons (simple boundary cycle, degree-3 Steiner vertices, maximally filled channels) are sufficient for exact distance realization.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same path-and-intersection language may decide distance realization for larger planar families once an appropriate “repelling” or “non-crossing” condition is identified.
  • Because the algorithm returns an explicit realizing graph whenever one exists, it immediately supplies a compact certificate of outerplanarity that can be verified independently of the dynamic program.
  • The non-existence of an O(1)-point condition suggests that any complete characterization of outerplanar metrics must involve global topological data of the same order as the number of terminals.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies the distance-realization problem for outerplanar graphs: given a metric D on a terminal set T of size k, decide whether there exists an edge-weighted outerplanar graph realizing the distances of D exactly, and construct one if so. Theorem 1 shows that, unlike trees and Okamura–Seymour instances, outerplanar metrics admit no O(1)-point characterization: for every k≥20 there is a non-outerplanar metric on k points whose every proper restriction is outerplanar (proved via the wheel metric and K4-minors). Theorem 2 supplies a constructive O(k^5)-time algorithm. The algorithm first recovers a circular ordering of the terminals (Section 3), then builds a canonical outerplanar graph together with a shortest-path structure that obeys the “repelling-paths condition” (every pair of terminal pairs that violate the four-point inequalities must be assigned disjoint paths). Sufficiency of this combinatorial condition for the existence of realizing edge lengths is established by a dual-flow argument, path-switching, and a pure uncrossing lemma on chord configurations (Lemma 9 and Section 4). The required structure is found by dynamic programming over boundary segments and channels (Section 5).

Significance. The result cleanly interpolates between the classical 4-point characterizations for trees/cacti and the Okamura–Seymour setting, while demonstrating that the absence of a local characterization need not preclude a polynomial-time algorithm. The “paths-and-intersections” viewpoint, the repelling-paths condition, and the chord-uncrossing lemma (Lemma 12) are of independent structural interest and already appear useful for related metric-realization and planar-emulator questions. The algorithm is fully constructive, self-contained (apart from a standard circular-order subroutine that is re-derived), and runs in O(k^5) time; the dual-flow feasibility proof is combinatorial rather than numerical. These features make the paper a solid contribution to algorithmic metric graph theory.

minor comments (4)
  1. The Ellipsoid-method runtime analysis at the end of Section 5 is stated as O(k^2)·O(k)·O(k^2)=O(k^5). A short remark that the bit-complexity of the separation oracle (all-pairs distances in an outerplanar graph with rational lengths) remains polynomial would make the claim fully rigorous.
  2. In the proof of Claim 11 the side-switching curve γ is defined with respect to the sets L and R; a one-sentence clarification that Property 5 already guarantees L∩R=∅ would help the reader follow the intersection-counting argument.
  3. Figures 2, 5 and 9 are referenced extensively; ensuring that the final camera-ready versions label the regions (1,2) and the three parallel edges of each channel would improve readability.
  4. A few typographical inconsistencies appear in the supplied text (e.g., “dist G”, missing spaces around subscripts, “O(k 5)”). These are easily cleaned in revision.

Circularity Check

1 steps flagged

No significant circularity: combinatorial proofs of repelling-paths sufficiency and DP are self-contained; only minor non-load-bearing self-citation for OS ordering subroutine.

specific steps
  1. self citation load bearing [Section 3 (circular ordering) and Lemma 9 proof (flow conversion)]
    "From previous work [CT25], there is an efficient algorithm that, given any Okamura-Seymour metric, determines the circular ordering... Using standard techniques [CT25], we can convert any pair F, F′ of flows..."

    CT25 is by the same authors. The citation supplies the OS ordering algorithm (re-used as a black-box subroutine) and a standard flow-alignment technique. However it is not load-bearing for the paper's novel content (repelling-paths sufficiency via uncrossing or the outerplanar DP); the authors re-prove the needed Claims 4–5/Observations and the dual argument is independent. Minor and does not force the main theorems.

full rationale

The paper's central claims (Theorem 1 via wheel-metric path intersections in Appendix A; Theorem 2 via circular order + repelling-paths Lemma 9 + DP) are derived from first-principles graph arguments. Lemma 9's sufficiency reduces LP feasibility (via Farkas dual flows) to a pure combinatorial statement: after path-switching to enforce Property 5 (potential on non-crossing pairs), chord configurations satisfy cut-metric dominance (Claim 11 via side-switching curve γ), and Lemma 12 (good-pair uncrossing for matchings + vertex-splitting reduction preserving dominance) plus Monge four-point forces the dual objective non-increasing, ruling out violation. All steps are proved in-line with no fitted parameters, no self-definitional equations, and no uniqueness imported to force the result. Section 3's circular-order subroutine cites CT25 (same authors) for the OS Monge algorithm and a flow-conversion technique, but re-proves the needed Claims 4–5, Observations 6–8, and runtime; this is a non-load-bearing subroutine (outerplanar is a special case of OS) and does not make the novel repelling/DP content circular. No ansatz smuggling or renaming of known results occurs. Honest non-finding of circularity is warranted.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 2 invented entities

The paper rests on standard metric and planar-graph axioms plus two combinatorial lemmas proved inside the text; no free parameters or external physical constants are introduced. The only non-standard entities are definitional (repelling pairs, canonical outerplanar graphs) and are fully characterized.

axioms (3)
  • domain assumption Four-point Monge property completely characterizes Okamura-Seymour metrics (used to recover circular order).
    Invoked in Section 3; taken from CO20/HLST88 and re-used without re-proof.
  • standard math Outerplanar graphs are K4-minor-free and admit a canonical form with degree-2 terminals and maximal channels.
    Standard structural facts used in the preprocessing of Section 5.
  • standard math Farkas lemma applied to the distance LP yields dual multi-commodity flows.
    Section 4; classical LP duality.
invented entities (2)
  • repelling paths condition no independent evidence
    purpose: Necessary and sufficient combinatorial certificate that a designated shortest-path structure admits realizing edge lengths.
    Defined after Lemma 3; proved equivalent to LP feasibility in Lemma 9.
  • canonical outerplanar graph (segments + channels) no independent evidence
    purpose: Normal form that reduces shortest-path structure search to a dynamic program over segment sequences.
    Constructed in Section 5 Step 1 by local rewiring; used as the search space for the DP.

pith-pipeline@v1.1.0-grok45 · 29701 in / 2065 out tokens · 20159 ms · 2026-07-12T12:10:33.041878+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Paths and Intersections: Recognizing Outerplanar Metrics." pith.science (2026). https://pith.science/paper/LJ4TOGQY

@misc{pith2026260625827,
  author       = {Pith},
  title        = {Pith review of: Paths and Intersections: Recognizing Outerplanar Metrics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LJ4TOGQY}},
  note         = {Machine review of arXiv:2606.25827}
}
Share X Bluesky LinkedIn Reddit HN
read the original 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.

Figures

Figures reproduced from arXiv: 2606.25827 by Yu Chen, Zihan Tan.

Figure 1
Figure 1. Figure 1: A canonical outerplanar graph: terminals [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Contracting all points oi,j into a supernode o, and splitting at o to obtain two graphs. We first prove that, after contraction, the shortest-path distance metric on terminals stays the same. Consider a terminal sℓ ∈ S. For any oij , since dist(oij , tj ) = βj , dist(sℓ , oij ) ≥ dist(sℓ , tj ) − dist(oij , tj ) = αℓ + βj − βj = αℓ . 6 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An illustration of path switching [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of Observations 6 (left), 7 (middle), and 8 (right). Left: the [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The i-(j + 1) path P (blue), and the curve γ along it (dashed green line). Claim 11. C ⪰ C ′ . Proof. Consider any cut (¯i, ¯j). On the one hand, by definition, distC(¯i, ¯j) = P (t,t′): crosses (¯i,¯j) Ft,t′. On the other hand, we show that distC′(¯i, ¯j) ≤ P (t,t′): crosses (¯i,¯j) Ft,t′. Assume that (¯i, ¯j) cuts the boundary into two segments (named left and right). Consider the i-(j + 1) path, which w… view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of path switching. paths Qd, R, and Pb, so Y is a d-b path. We say that X, Y are obtained by switching paths P, Q. See [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A canonical outerplanar graph: boundary segments [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 5
Figure 5. Figure 5: The i-(j + 1) path P (blue), and the curve γ along it (dashed green line). Claim 11. C ⪰ C ′ . Proof. Consider any cut (¯i, ¯j). On the one hand, by definition, distC(¯i, ¯j) = P (t,t′): crosses (¯i,¯j) Ft,t′. On the other hand, we show that distC′(¯i, ¯j) ≤ P (t,t′): crosses (¯i,¯j) Ft,t′. Assume that (¯i, ¯j) cuts the boundary into two segments (named left and right). Consider the i-(j + 1) path, which w… view at source ↗
Figure 6
Figure 6. Figure 6: Massaging an outerplanar graph into a canonical one. [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The subproblem Π[i, j]. The Si-Sj channel (black) is enforced. The dynamic programming algorithm. We now describe the algorithm for computing the entries in the dynamic programming table. The base case is the entries Π[i, i + 1] for all i ≤ k − 1. In these subproblems, there are no channels to add, and the shortest paths are: the ti-ti+1 shortest path is Si , the ti+1-ti+2 shortest path is Si+1; and the ti… view at source ↗
Figure 7
Figure 7. Figure 7: Massaging an outerplanar graph into a canonical one. [PITH_FULL_IMAGE:figures/full_fig_p017_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The construction of the final outerplanar graph and the shortest path structure. [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 8
Figure 8. Figure 8: The subproblem Π[i, j]. The Si-Sj channel (black) is enforced. The dynamic programming algorithm. We now describe the algorithm for computing the entries in the dynamic programming table. The base case is the entries Π[i, i + 1] for all i ≤ k − 1. In these subproblems, there are no channels to add, and the shortest paths are: the ti-ti+1 shortest path is Si , the ti+1-ti+2 shortest path is Si+1; and the ti… view at source ↗
Figure 9
Figure 9. Figure 9: An illustration of Case 5.1. and the two second subpaths may intersect once. We show that the intersections cannot both happen. Assume for contradiction that the tx1 -ti subpath and the tx2 -tℓ+1 subpath intersect at a segment Sz, and the tj+1-ty2 subpath and the tℓ-ty1 subpath intersect at a segment Sw. Case 5.3.1. Sz lies between tx2 and tℓ , and Sw lies between tℓ+1 and ty2 . In this case, (tx2 , ty2 ) … view at source ↗
Figure 9
Figure 9. Figure 9: The construction of the final outerplanar graph and the shortest path structure. [PITH_FULL_IMAGE:figures/full_fig_p020_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: The outerplanar graph realizing the metric [PITH_FULL_IMAGE:figures/full_fig_p024_10.png] view at source ↗
Figure 10
Figure 10. Figure 10: An illustration of Case 5.1. Case 5.2. y1 ≤ y2, the tx1 -ty1 path visits Si , Sj , and the tx2 -ty2 path visits Sℓ . Same as 5.1. Case 5.3. y1 ≥ y2. In this case, the only possibility is that the tx1 -ty1 path visits Si and Sj , while the tx2 -ty2 path visits Sℓ , since otherwise we can get a contradiction by Observation 6. As both paths are the concatenation of two subpaths, by induction hypothesis, the … view at source ↗
Figure 11
Figure 11. Figure 11: The outerplanar graph realizing the metric [PITH_FULL_IMAGE:figures/full_fig_p024_11.png] view at source ↗

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Paths and Intersections: Minimum Realization of Okamura-Seymour Instances

    cs.DS 2026-07 accept novelty 7.0

    Every OS metric has a unique minimum-crossing medial template; its primal arrangements are precisely the fewest-edge disk realizations, recoverable with realizing lengths in polynomial time.

Reference graph

Works this paper leans on

6 extracted references · 2 linked inside Pith · cited by 1 Pith paper

  1. [1]

    A local-to-global theorem for congested shortest paths

    [AW22] Shyan Akmal and Nicole Wein. A local-to-global theorem for congested shortest paths. arXiv preprint arXiv:2211.07042,

    Pith/arXiv arXiv

  2. [2]

    Graph realization of distance sets

    [BNPPR22] Amotz Bar-Noy, David Peleg, Mor Perry, and Dror Rawitz. Graph realization of distance sets. In47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Schloss-Dagstuhl-Leibniz Zentrum f¨ ur Informatik,

    2022

  3. [3]

    On the structure of unique shortest paths in graphs

    [Bod19] Greg Bodwin. On the structure of unique shortest paths in graphs. InProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2071–2089. SIAM,

    2071

  4. [4]

    Planar emulators for monge matrices

    [CO20] Hsien-Chih Chang and Tim Ophelders. Planar emulators for monge matrices. In J. Mark Keil and Debajyoti Mondal, editors,Proceedings of the 32nd Canadian Conference on Computational Geometry, CCCG 2020, August 5-7, 2020, University of Saskatchewan, Saskatoon, Saskatchewan, Canada, pages 141–147,

    2020

  5. [5]

    Path and intersections: Characterization of quasi-metrics in directed okamura-seymour instances

    [CT25] Yu Chen and Zihan Tan. Path and intersections: Characterization of quasi-metrics in directed okamura-seymour instances. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2467–2490. SIAM,

    2025

  6. [6]

    Paths and intersections: Exact emulators for planar graphs.arXiv preprint arXiv:2507.09620,

    [LTZ25] George Z Li, Zihan Tan, and Tianyi Zhang. Paths and intersections: Exact emulators for planar graphs.arXiv preprint arXiv:2507.09620,

    Pith/arXiv arXiv