{"id":"1c452b99-018d-480c-82a4-00c4b38e8606","arxiv_id":"2606.25827","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Outerplanar metrics admit an O(k^5) recognition algorithm but no O(1)-point local characterization, proved via a repelling-paths condition on shortest-path structures.","lead":"The paper gives a polynomial-time algorithm deciding whether a metric on k terminals is realized by some edge-weighted outerplanar graph, and proves no constant-size local condition can characterize such metrics. The result fills the gap between trees/cacti and Okamura-Seymour instances using a paths-and-intersections analysis.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The central claim (poly-time recognition + construction of outerplanar metrics, plus absence of an O(1)-point condition) rests on three cleanly separated pieces: circular-order recovery (Section 3), the combinatorial characterization of feasible edge lengths by the repelling-paths condition (Lemma 9), and a DP that produces a structure satisfying that condition (Section 5). The dual-flow / uncrossing argument that establishes sufficiency of the condition is the only non-routine step; it is written out in full detail with explicit potential, cut-curve construction, good-pair analysis, and a reduction that preserves dominance. No hidden assumption, omitted case, or circular appeal is apparent. The impossibility result (wheel metric) is elementary and independent. Consequently the reader's ACCEPT / HIGH / low-risk assessment stands; the concrete verification above is merely a sanity check that a careful reader can perform by hand on small matchings.","tokens_in":25543,"tokens_out":528,"duration_ms":6155,"concrete_test":"Independently re-derive the special-case uncrossing of Lemma 13: start from an arbitrary pair of perfect matchings C ≻ C' on 2n points, locate a good pair by the minimal-segment argument of Claim 14-15, uncross it, and verify that every cut distance that decreases still remains at least as large as the corresponding distance in C'. If any counter-example configuration appears, Lemma 12 (and therefore LP feasibility) fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest assumption (sufficiency of the repelling-paths condition via Lemma 9 / dual-flow uncrossing) is the natural load-bearing point, but the manuscript supplies a complete, self-contained argument: Farkas dual, integral path-switching that preserves Properties 1-4 while enforcing Property 5 (potential on non-crossing pairs), cut-metric dominance of the resulting chord configurations (Claim 11 via the side-switching curve γ), and the pure combinatorial Lemma 12 (good-pair uncrossing for matchings + vertex-splitting reduction that preserves dominance). The four-point Monge property then forces the weighted sum of D-values to be non-increasing under uncrossing, ruling out a violating dual. No internal gap or missing case is visible; the DP of Section 5 correctly reduces the remaining combinatorial search to segment sequences that already satisfy the strongest (segment-related) repelling conditions.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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).","tokens_in":25782,"tokens_out":761,"duration_ms":15364,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a natural journal version of recent SODA-style work on path systems; it fits well in a theory journal that publishes algorithmic graph theory and metric embeddings. No novelty or citation concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles the natural open case between trees/cacti and Okamura-Seymour: outerplanar metrics have no O(1)-point condition (Theorem 1, wheel-metric K4-minor argument) yet are recognizable in O(k^5) time (Theorem 2). That combination is new and useful for metric graph theory.\n\nWhat works well is the structural pipeline. They recover a circular order (Section 3, reusing and simplifying their earlier OS subroutine), reduce to a canonical outerplanar graph of segments plus non-crossing channels, then run a clean DP over segment sequences that already enforce the strongest (segment-related) repelling conditions. The key technical claim is Lemma 9: a designated shortest-path structure satisfies the distance LP if and only if every repelling pair of terminal pairs has disjoint paths. The sufficiency direction is proved by Farkas dual, integral path-switching that preserves flow properties while enforcing non-crossing, cut-metric dominance via a side-switching curve, and a pure combinatorial uncrossing lemma on chords (Lemma 12, good-pair argument plus vertex-splitting reduction). The four-point Monge property then forces the dual objective to be non-increasing, so no violating dual exists. The argument is self-contained and the stress-test concern does not land; the cases check out.\n\nSoft spots are minor and proportional. Runtime claims for the Ellipsoid step with APSP separation are a bit hand-wavy (still O(k^5) overall), and the DP correctness relies on three short observations about non-repelling pairs that are proved only in the appendix. Neither threatens the main theorems. Citations are appropriate; self-cites to CT25 are limited to the order-recovery black box that is re-proved here.\n\nThis is for people who work on distance realization, planar metrics, or structural graph algorithms. The paths-and-intersections viewpoint is the piece most likely to travel. It deserves a serious referee and should be accepted after ordinary polishing. I would cite the recognition algorithm and the uncrossing lemma.","headline":"Solid poly-time recognition for outerplanar metrics plus a clean no-local-characterization result; the paths-and-intersections machinery is the real reusable piece.","tokens_in":26330,"tokens_out":524,"would_cite":true,"duration_ms":5150,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","68Q25","90C05"],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["outerplanar graphs","distance realization","metric embedding","shortest paths","Okamura–Seymour","dynamic programming","path intersections"],"falsifier":"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.","tokens_in":26479,"feed_emoji":"📐","tokens_out":949,"duration_ms":8796,"temperature":0.7,"pith_summary":"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.","feed_headline":"Outerplanar metrics recognized in O(k^5) time","feed_subtitle":"No constant-point test exists, yet path intersections decide the problem completely","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["No local test yet O(k^5) decides outerplanar metrics","Path intersections yield O(k^5) outerplanar metric check","Outerplanar metrics recognized via canonical path DP","Repelling pairs and dual flows settle outerplanar metrics","Graphs as path intersections unlock outerplanar recognition"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["No local test yet O(k^5) decides outerplanar metrics","Path intersections yield O(k^5) outerplanar metric check","Outerplanar metrics recognized via canonical path DP","Repelling pairs and dual flows settle outerplanar metrics","Graphs as path intersections unlock outerplanar recognition"]},"model":"grok-4.5","effort":"low","cost_usd":0.004644,"raw_usage":{"total_tokens":1226,"prompt_tokens":678,"num_sources_used":0,"completion_tokens":62,"cost_in_usd_ticks":46440000,"prompt_tokens_details":{"text_tokens":678,"audio_tokens":0,"image_tokens":0,"cached_tokens":0},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":486,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":678,"tokens_out":62,"duration_ms":5133,"temperature":1.0,"reasoning_tokens":486,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T12:10:33.041878+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":2}