{"id":"a8b59ac2-26c0-49b4-9e84-58ddb4121600","arxiv_id":"2607.02883","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"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.","lead":"Any Okamura-Seymour metric determines a unique medial chord template whose arrangements are exactly the minimum-edge disk graphs realizing the metric. This gives a polynomial algorithm that recovers the sparsest planar realizations of given cyclic boundary distances.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The paper's central claim is a clean combinatorial characterization: every OS metric D determines a unique medial template Φ(D) via the cut numbers b_{x,y}, and the minimum-edge realizations are precisely the primal graphs of arrangements of that template, each of which admits efficiently computable realizing lengths. The only place this could fail is if the chain inequalities of Theorem 5 did not fully characterize the existence of a D-good shortest-path structure, because every subsequent argument (feasibility of Φ(D), uncrossing minimality, and length recovery via Lemma 3) invokes that equivalence. The inductive construction of the paths Π[i,j], the matching certificates of Claim 6, the contradiction for bad pairs in Claim 7, and the subpath property proved via Observation 8 are written out in full and appear free of gaps. The parallel with critical electrical networks is only motivational; the distance-side arguments are self-contained. Consequently the reader's ACCEPT verdict with high confidence stands; no adjustment is warranted.","tokens_in":16489,"tokens_out":523,"duration_ms":5662,"concrete_test":"Independently re-derive the two inductive steps of Claim 6 (Case 1 strip augmentation and Case 2 inheritance) and the first-irregular-pair exchange of Lemma 10 on a concrete 6-terminal OS metric whose a_{x,y} values are known by exhaustive enumeration of repelling sets; confirm that the resulting b-vector produces a perfect matching via formula (4) whose arrangements realize D with exactly cr(Φ) edges.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest assumption (Theorem 5's inductive characterization of D-good shortest-path structures via chain inequalities) is the correct load-bearing point, but the case analysis appears complete. Claim 6 builds matching repelling sets and chains by induction on the two construction cases for Π[i,j]; Claim 7 derives a strict chain violation from any bad pair; Observation 8 and the subsequent nested-interval induction establish the subpath-intersection property; Observation 2 supplies the needed non-repulsion transitivity. These pieces close both directions of Theorem 5, so the later uniqueness of Φ(D) (Lemma 13), minimality of its crossing number (Theorem 15), and the exact identification of minimum primal graphs (Lemma 16 / Theorem 19) rest on solid ground. No hidden gap that would invalidate the central claim is visible.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper solves the minimum-edge realization problem for Okamura–Seymour metrics: given a Kalmanson metric D on a cyclically ordered terminal set T, recover all disk-embedded graphs with the fewest edges that realize D as shortest-path distances with the prescribed boundary order. The authors introduce repelling pairs (metric certificates of forced path separation), prove that an OS instance admits a D-good shortest-path structure if and only if every repelling set M and every chain A satisfy |M| ≤ |A| (Theorem 5), and show that the resulting cut numbers a_{x,y} (after endpoint correction to b_{x,y}) determine a unique medial template Φ(D) via circular inversion (Lemma 13). Minimum realizations are exactly the primal graphs of arrangements of Φ(D) (Lemma 16), each having cr(Φ(D)) edges; for any such graph, nonnegative edge lengths realizing D can be computed efficiently (Theorem 19). The development is paralleled with the inverse problem for electrical networks (Table 1).","tokens_in":16646,"tokens_out":787,"duration_ms":27628,"significance":"The result gives a complete structural and algorithmic solution for minimum OS realizations: a canonical template is recovered from D alone, all minimal embedded graphs are identified as arrangements of that template, and realizing lengths are efficiently obtainable. The paths-and-intersections viewpoint, the characterization via repelling pairs and chains, and the exact parallel with critical electrical networks are of independent interest for metric graph theory and planar algorithms. The claims are constructive and the non-uniqueness of lengths is correctly exhibited (Appendix A). If the polynomial-time claims hold, the paper supplies a clean, usable compression of OS metrics.","major_comments":[],"minor_comments":[{"comment":"Theorem 1 and the opening of Section 4 assert that the template (hence all a_{x,y}/b_{x,y}) can be computed in polynomial time, yet no explicit procedure is given for evaluating the maximum size of a mutually repelling set of pairs that cross a given cut. While Observation 2 and the ordered-exchange arguments of Lemma 10 suggest a greedy or DP algorithm exists, a short paragraph or reference confirming poly-time computability would make the efficiency claim self-contained.","section":null},{"comment":"Figure 1 caption refers to “path Π[i+1, j+1] (red)”; the surrounding text and construction use Π[i+1, j−1]. Correct the index.","section":null},{"comment":"The concurrent preprint [CT26] is cited for Lemma 3 and for the uncrossing lemma used in Theorem 15. A one-sentence statement of the precise statements borrowed would help readers who do not yet have access to that manuscript.","section":null},{"comment":"In the definition of chains (Definition 4) the length |A| counts only vertices; a parenthetical reminder that peripheral regions contribute zero would reduce the chance of off-by-one confusion when the endpoint correction for b_{x,y} is introduced.","section":null},{"comment":"Table 1 is helpful; adding a one-line pointer in the caption to the precise theorems that justify each row of the “Distance realization” column would improve readability.","section":null}],"recommendation":"accept","confidential_remarks":"The concurrent self-citation [CT26] is used for two load-bearing black-box lemmas. The present manuscript is self-contained once those lemmas are granted, but an editor may wish to confirm that the two papers do not form a circular dependency before final acceptance. Otherwise the contribution is clean and the technical development appears solid."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles the minimum-edge realization problem for Okamura–Seymour / Kalmanson metrics. The new object is the canonical medial template Φ(D) built from the cut numbers b_{x,y} that come from maximum repelling sets; every min-edge disk embedding is a primal arrangement of that template, the edge count is exactly the number of crossings, and realizing lengths can be recovered in poly time.\n\nWhat works: the parallel with the electrical-network inverse theory is drawn carefully and is useful. The chain of arguments is fully written—repelling pairs give forced separations, those become chain lower bounds, the b numbers invert uniquely to a perfect matching on the medial endpoints, and uncrossing shows it is the unique min-crossing feasible template. Section 3’s inductive construction of a good shortest-path structure (the load-bearing Theorem 5) looks complete on a careful read: Claim 6 builds matching sets and chains, Claim 7 kills bad pairs, Observation 8 plus the nested-interval induction give the subpath property, and Observation 2 supplies the needed non-repulsion transitivity. The later uniqueness and minimality theorems rest on that foundation without circularity. Algorithms are explicit; no free parameters.\n\nSoft spots are minor and local. The path-intersection case analysis is delicate and long; a referee will want to check every subcase of Observation 8 and the bad-pair argument, but nothing jumps out as broken. Edge lengths are not unique (they give a clean 8-terminal example), which the paper already flags. Self-citations to concurrent outerplanar work are present but not load-bearing.\n\nThis is for people who care about metric graph theory, planar multicommodity flow, or inverse network problems. It is a solid, self-contained combinatorial result that advances a classical line. I would send it to peer review without hesitation; the central claim is supported and the proofs are there to be checked.","headline":"Clean combinatorial solution: OS metrics determine a unique minimum-crossing medial template whose arrangements are exactly the min-edge realizations.","tokens_in":17278,"tokens_out":472,"would_cite":true,"duration_ms":5270,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","05C85","68R10","90C35"],"pacs":[],"model":"grok-4.5","headline":"Every Okamura–Seymour metric has a unique medial template whose arrangements give all minimum edge-count realizations, with lengths computable in polynomial time.","keywords":["Okamura-Seymour instances","minimum realization","Kalmanson metrics","medial graphs","repelling pairs","shortest-path metrics","Y-Δ transformations","disk-embedded graphs"],"falsifier":"Exhibit an OS metric D and a disk graph G that satisfies every chain inequality |M| ≤ |A| yet fails to admit any family of paths that are simultaneously vertex-disjoint on all repelling pairs and whose pairwise intersections are single subpaths; or produce two distinct templates both achieving the minimum crossing number for the same b_{x,y} numbers.","tokens_in":17361,"feed_emoji":"🔗","tokens_out":865,"duration_ms":13841,"temperature":0.7,"pith_summary":"An Okamura–Seymour metric records shortest-path distances among terminals that sit on the boundary of a disk. The paper asks for the sparsest disk-embedded graphs that realize those distances exactly. It shows that the metric itself forces a single canonical matching of boundary points—the medial template—and that every minimum-edge realization is simply the primal graph of some arrangement of that template. The same template also supplies the exact minimum edge count. For any such graph the authors construct a good family of shortest paths and then recover nonnegative edge lengths that realize the metric. The argument treats the graph as a system of paths and their forced intersections, using repelling pairs as certificates that certain paths must stay vertex-disjoint.","feed_headline":"One medial template yields all minimum OS realizations","feed_subtitle":"Distance data alone force a unique chord matching whose arrangements are the sparsest realizing graphs","key_machinery":"The medial template Φ(D): the unique perfect matching on alternating boundary points whose crossing numbers equal the corrected repelling cut sizes b_{x,y}. Arrangements of this template produce all minimum primal graphs, because crossings of medial chords become edges and the cut inequalities of Theorem 5 become tight.","core_discovery":"For any OS metric D the cut numbers b_{x,y} derived from maximum repelling sets determine a unique medial template Φ(D). The graph structures of all minimum realizations of D are exactly the primal graphs of arrangements of Φ(D); each has precisely cr(Φ(D)) edges, and nonnegative lengths realizing D can be computed efficiently on every such graph.","pith_inferences":["The same path-and-intersection viewpoint may yield minimum realizations for other planar or outerplanar metric families once suitable repelling certificates are defined.","Because the medial template is uniquely determined by local cut data, it supplies a compact certificate of structural complexity that could be used for metric compression or network tomography on disk-like topologies.","If the inductive construction of good paths can be derandomized or made fully combinatorial, the algorithm becomes a purely combinatorial reconstruction procedure with no numerical linear algebra."],"forward_implications":["All minimum OS realizations of a given metric share the same number of edges, equal to the crossing number of Φ(D).","The distinct embedded graphs realizing a metric with the fewest edges are related by Y–Δ moves that preserve the medial pairing.","Both the template and one concrete weighted realization can be recovered in polynomial time from the distance matrix alone.","Edge lengths realizing D on a fixed minimum graph need not be unique, even though the combinatorial structure is canonical."],"fun_headline_variants":["OS metric forces unique medial template for all min realizations","Canonical medial template yields every minimum OS realization graph","Min OS realizations are primals of one medial template's arrangements","Cut numbers alone determine medial template of sparsest OS graphs","Paths and intersections recover all minimum OS realization graphs"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The claim rests on the equivalence that a graph admits a good shortest-path structure if and only if no repelling set of pairs crosses any chain more times than the chain’s length.","fun_headline_variants_meta":{"raw":{"variants":["OS metric forces unique medial template for all min realizations","Canonical medial template yields every minimum OS realization graph","Min OS realizations are primals of one medial template's arrangements","Cut numbers alone determine medial template of sparsest OS graphs","Paths and intersections recover all minimum OS realization graphs"]},"model":"grok-4.5","effort":"low","cost_usd":0.003686,"raw_usage":{"total_tokens":1129,"prompt_tokens":676,"num_sources_used":0,"completion_tokens":60,"cost_in_usd_ticks":36860000,"prompt_tokens_details":{"text_tokens":676,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":393,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":676,"tokens_out":60,"duration_ms":4473,"temperature":1.0,"reasoning_tokens":393,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T06:23:33.338493+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit an OS metric D and a disk graph G that satisfies every chain inequality |M| ≤ |A| yet fails to admit any family of paths that are simultaneously vertex-disjoint on all repelling pairs and whose pairwise intersections are single subpaths; or produce two distinct templates both achieving the minimum crossing number for the same b_{x,y} numbers.","supporting_citations":[],"review_version":1}