{"id":"0a311d2f-d737-41b9-bd00-d2a0a7d3ee67","arxiv_id":"2507.09620","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Every edge-weighted planar graph with k terminals on f faces is claimed to admit an exact planar emulator of size O(f^2 k^2), interpolating known O(k^2) and O(k^4) bounds.","lead":"This paper gives a new size bound for exact planar emulators: when k terminals lie on f faces of a planar graph, a smaller planar graph with O(f^2 k^2) vertices can preserve all terminal distances exactly. The result interpolates between the known single-face O(k^2) and general O(k^4) bounds, but the proof has gaps that leave the theorem unestablished as written.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Observation 28's Wye-Delta min-cut computation is incorrect unless an unstated triangle inequality holds; no proof of that inequality is given for the path capacities, so Claim 27 and the flow-morphing proof of Claim 20 are unsupported.","rationale":"The central theorem depends on the edge-weight construction in Lemma 18, whose proof is a Farkas/duality argument. The only bridge from flows in H* to flows in G is Claim 20, and Claim 20 is proved by the morphing process whose local invariant is Claim 27. Claim 27's only nontrivial step is the Wye-Delta equivalence in Observation 28. The min-cut computation there is objectively incorrect unless a triangle inequality holds, and the paper neither states nor proves it. The capacities are dual variables, so no inherent triangle inequality is available. This is therefore a genuine gap in the submitted argument, not a disagreement with consensus or a stylistic issue. I agree with the reader's diagnosis and would not change the REJECT verdict, though the main theorem may be repairable. The Delta-Wye direction (triangle to Y with capacities such as c(u,v)+c(u,w)) is unconditionally valid, so the idea is not hopeless, but the Wye-Delta direction used in the proof is not justified. The paper does contain useful independent ideas, including the path/intersection viewpoint and the LP framework, but as written the correctness argument for the main theorem does not go through.","tokens_in":30741,"tokens_out":17521,"duration_ms":201813,"concrete_test":"Perform the Wye-Delta cut computation with capacities (c(x,u), c(x,v), c(x,w)) = (1,1,3): in the Y, the cut separating {u,v} from {w} has value min(3, 1+1)=2, while the claimed triangle has value c(u,w)+c(v,w)=3, so the two are not flow-equivalent. Then check whether any condition in Sections 4.2-4.3, such as flow dominance or the cost inequality from Claim 20, rules out such a triple for the paths in Figure 28; if such a triple is admissible, Observation 28 is genuinely load-bearing and Claim 27 is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.3 proves Claim 20 by morphing the flow from H* into G, and the local invariant is Claim 27, which says the F' demands remain routable after rerouting a canonical path over a closest crossing. The only substantive step in Claim 27 is Observation 28, specifically the Wye-Delta direction: replacing a degree-three non-terminal x with a triangle on u,v,w is claimed to preserve terminal-flow equivalence, and the proof asserts that the minimum cut separating u from {v,w} in the Y is c(x,u). In fact, the cut may put x on either side, so the value is min(c(x,u), c(x,v)+c(x,w)). The stated equality with the triangle cut c(u,v)+c(u,w)=c(x,u) requires c(x,u) ≤ c(x,v)+c(x,w); applying the same reasoning to all three terminals means the capacities must satisfy triangle inequalities, which is exactly what makes the transformed Delta edge capacities nonnegative. No argument in the paper derives these inequalities for the capacities a,b,c of the three local paths gamma, gamma_b, gamma_c in Figure 28; they are arbitrary nonnegative dual variables from Claim 19. For capacities (1,1,3), the Delta capacity (1+1-3)/2 is negative, and the cut separating {u,v} from {w} has value min(3,2)=2 in the Y but 3 in the claimed Delta. Thus the local flow equivalence is false as stated. Since Observation 28 carries Claim 27, which carries Claim 20, the edge-weight proof of Lemma 18 and hence Theorem 1 is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes exact planar distance emulators of size O(f^2 k^2) for k terminals lying on f faces, a result that would interpolate the known O(k^2) single-face bound and the known O(k^4) general bound. The construction first simplifies the input graph, extracts O(f) critical paths per terminal, forms a skeleton H* from their intersections, and defines canonical paths between terminals on different faces. Edge weights are then obtained by proving feasibility of a linear program; using Farkas' lemma, feasibility is reduced to a statement about terminal flows (Claim 19), and the main technical work (Claims 20 and 27) is to morph flows from H* into the original graph G. The paper concludes that H preserves terminal distances exactly.","tokens_in":31011,"tokens_out":9432,"duration_ms":114189,"significance":"If Theorem 1 were established, it would give a clean interpolation between the single-face and general planar emulator bounds, and it would further develop the paths-and-intersections viewpoint introduced in [CT25]. The skeleton construction and the LP-duality framework are original and clearly described, and the paper is explicit about borrowing the one-face emulator construction from [CO20] and [GHP20]. The main obstacle is correctness: the proof of the central flow-morphing claim rests on a false local statement, so the main result is not established by the submitted manuscript.","major_comments":[{"comment":"Observation 28 is false as stated. In a Y-shaped subgraph with a degree-three non-terminal x connected to terminals u,v,w with capacities c(x,u), c(x,v), c(x,w), the minimum cut separating u from {v,w} is min(c(x,u), c(x,v)+c(x,w)), not simply c(x,u), because the cut may place x on either side. For example, with capacities (3,1,1), the Y has a u-to-{v,w} cut of value 2, while the claimed Delta triangle has cut value c(u,v)+c(u,w)=3. In addition, the Wye-Delta capacity formulas can produce negative values, e.g., for capacities (1,1,3) the edge (v,w) would be assigned (1+1-3)/2 < 0. The formulas only define a valid capacitated graph if the path capacities a,b,c satisfy triangle inequalities, and no such inequalities are proved for the capacities appearing in Figure 28.","section":"§4.3, Observation 28"},{"comment":"Claim 27 is the only mechanism that maintains routability of the F' demands during the flow-morphing process, and its proof relies entirely on the Wye-Delta equivalence asserted in Observation 28. Since Observation 28 is false, the local flow equivalence between the old and new graphs in Figure 28 is not established. Consequently Claim 20, which converts the dual flows in H* into flows in G, is unsupported, and Lemma 18, on which Theorem 1 depends, is not proven.","section":"§4.3, Claim 27 and Figure 28"},{"comment":"Even apart from the incorrect min-cut computation, the reduction from global flow equivalence to local cut equivalence is not fully justified. The proof invokes Okamura-Seymour for the induced subgraphs on {u,v,w} and {u,v,w,x}, but the argument that a flow in the whole graph can be decomposed as a residual flow in the rest of the graph plus a flow through the local structure requires that the residual demand after removing the local edge flows be supported on {u,v,w}. The manuscript asserts this without a careful treatment of flows that enter or leave the local structure through x, and the notation f' is used for edges (u,v),(u,w),(v,w) even though these edges do not exist in the original Y graph. This part of the proof needs to be rewritten even if the cut computation were corrected.","section":"§4.3, Proof of Observation 28"}],"minor_comments":[{"comment":"There is a grammatical error in the sentence 'we remove from G all edges from that does not participate in any shortest path connecting a pair of terminals'; it should read 'edges from G that do not participate'.","section":"§3.1, Step 1"},{"comment":"The definition of Area for pairs of critical paths is given informally with reference to figures; a formal definition in terms of the planar embedding would improve rigor, especially since the later proofs rely on containment and subset relations among these areas.","section":"§3.4.1, Areas"},{"comment":"The proof refers to 'the counterclockwise segment between t'_{j1-1} and t'_{j3+1}' without specifying the indexing convention modulo the number of terminals on the face; this should be stated explicitly.","section":"Appendix A.2, Proof of Observation 3"},{"comment":"The statement 'the minimum cut separating u from v and w' would be clearer as 'separating u from {v,w}', since v and w are treated as a single group in the relevant partition.","section":"§4.3, Observation 28"}],"recommendation":"reject","confidential_remarks":"The false statement in Observation 28 is load-bearing and appears to require a substantially new argument for Claim 27 rather than a local correction. The skeleton construction and the LP-duality approach may still be valuable, and I would be willing to consider a revised version if the authors can supply a correct flow-morphism proof or derive the missing capacity inequalities."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result—exact planar emulators of size O(f^2 k^2) when terminals lie on f faces—is the right next step after the O(k^2) single-face and O(k^4) general cases. The critical-path skeleton, with O(f) critical paths per terminal, is a genuinely new organizing idea, and the LP-dual framing is clean: reduce the feasibility of the weight LP to a flow non-existence statement, then morph flows from the skeleton into the original graph. The graph-splitting phase (Lemma 21 and the flow-packing argument) looks sound to me on a first read.\n\nBut the load-bearing step in the flow morphing is not sound. Observation 28 claims that the Wye-Delta transformation preserves terminal-flow equivalence, and the proof asserts that the minimum cut separating u from {v,w} in the Y-structure is c(x,u). That is only correct when c(x,u) ≤ c(x,v)+c(x,w). In general, the cut that puts x on the {v,w} side has value c(x,v)+c(x,w), and the Delta edge capacities can go negative without the triangle inequality. The capacities here are flow values from Claim 19—arbitrary nonnegative variables—so the needed inequalities do not hold automatically. Observation 28 is false as stated, and since Claim 27's local flow-equivalence argument relies on it, Claim 20 and hence Lemma 18 are unsupported. This is not a cosmetic gap; it is the central edge-weight argument.\n\nThere are also smaller issues: several geometric claims in Section 3 (Claim 10, Claim 15, Observation 16) are justified only by figures and informal case analysis. That is a verification burden, not a fatal flaw, but it adds risk.\n\nThe theorem might still be true and the approach repairable—one plausible route is to argue the capacities inherit triangle inequalities from the flow structure, though the text does not do that. As submitted, though, the proof does not go through. I would still send it to referees, because the problem is important and the skeleton construction is a real idea. A careful referee might find a repair or might bury it. I would not cite the theorem as established until the flow-morphing argument is fixed.\n\nReading-group value: this is a good case study in how a small cut-equivalence mistake can sink a large proof.","headline":"The f-face emulator result is a natural target and the skeleton construction is genuinely new, but the Wye-Delta min-cut calculation in Observation 28 is wrong, and that error sinks the flow-morphing proof of the edge-weight lemma.","tokens_in":31655,"tokens_out":3364,"would_cite":false,"duration_ms":34328,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C12","05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every edge-weighted planar graph with $k$ terminals lying on $f$ faces has an exact planar emulator with $O(f^2 k^2)$ vertices.","keywords":["planar graphs","vertex sparsification","distance emulators","exact emulators","critical paths","canonical paths","linear programming feasibility","Wye-Delta transformation"],"falsifier":"Recompute the minimum cut separating $u$ from $\\{v,w\\}$ in the Y-shaped graph with edge capacities $c(x,u)$, $c(x,v)$, and $c(x,w)$. If that cut value is the smaller of $c(x,u)$ and $c(x,v)+c(x,w)$ rather than $c(x,u)$, then the claimed equality between the Y and $\\Delta$ cuts in the Wye-$\\Delta$ step fails, and the flow-morphing proof must supply a different local argument before the theorem's weight-setting lemma is established.","tokens_in":30429,"feed_emoji":"🕸️","tokens_out":11419,"duration_ms":118762,"temperature":0.7,"pith_summary":"This paper aims to prove that an edge-weighted planar graph with $k$ terminals all lying on the boundaries of $f$ faces can be compressed to a planar graph on $O(f^2 k^2)$ vertices that exactly preserves every terminal-to-terminal distance. The result would generalize the known $O(k^2)$ construction for terminals on one face and the $O(k^4)$ construction for the general case, suggesting that the number of faces is the right structural parameter. The construction first extracts a small set of 'critical' shortest paths per terminal and records how they cross, then proves by linear-programming duality that edge weights realizing the terminal distances exist. The proof's hard part is showing that certain terminal flows cannot exist, which is done by morphing paths in the skeleton back to paths in the original graph while preserving flow dominance.","feed_headline":"Exact planar emulators shrink to O(f²k²)","feed_subtitle":"With k terminals spread over f faces, all pairwise distances survive in a planar graph of size O(f²k²).","key_machinery":"The central machinery is the path-intersection viewpoint: the paper treats a graph as a family of terminal-to-terminal shortest paths together with the pattern of their crossings, rather than as a set of vertices and edges. From each terminal it keeps $O(f)$ 'critical' shortest paths, defined as the paths whose shape changes when the other endpoint scans over a terminal face; these are paired into primary and secondary paths, and the route between any two terminals is the canonical path formed by concatenating primary subpaths up to a bend. The skeleton is then drawn so that critical paths cross at most once, and edge weights are certified by a linear program ($LP$-$H^*$) whose feasibility is proved through linear-programming duality and flow dominance: infeasibility would create terminal flows $F$ dominating $F'$ with lower cost, and the proof shows these cannot exist by morphing canonical paths back to the original shortest paths through 'M-Areas', using Wye-$\\Delta$ transformations to keep the capacity structure locally unchanged.","core_discovery":"The paper's central claim is Theorem 1: for every edge-weighted planar graph $G$ with terminal set $T$ of size $k$ lying on $f$ faces of the embedding, there is an edge-weighted planar graph $H$ with $T \\subseteq V(H)$ and $|V(H)| = O(f^2 k^2)$ such that $dist_H(t,t') = dist_G(t,t')$ for all $t,t' \\in T$. The construction builds a central skeleton $H^*$ from critical paths and glues one-face emulators into its faces; distances between terminals on different faces are preserved by $H^*$, and distances on the same face by the one-face pieces. The theorem would place the known single-face bound $O(k^2)$ and the general bound $O(k^4)$ on a common curve indexed by the number of faces, with every intermediate value covered.","pith_inferences":["A direct consequence the paper leaves implicit is that the same $O(f^2 k^2)$ skeleton could serve distance queries between non-terminal vertices that also lie on those $f$ faces, since the skeleton is built from the same shortest-path structure.","If the local flow-equivalence step in the Wye-Delta argument is repaired, the statement of Theorem 1 would remain plausible, because the construction and the size bound do not depend on that local calculation.","The face-count parameter suggests a testable extension: worst-case planar instances may force emulators of size $\\Omega(f^2 k^2)$, which would make the quadratic dependence on $f$ necessary rather than an artifact of the proof.","The existential LP-feasibility certificate could become a polynomial-time construction if a separation oracle for the dual flow conditions is found, potentially yielding an algorithmic version of the emulator construction."],"forward_implications":["If Theorem 1 is correct, the single-face bound $O(k^2)$ and the general bound $O(k^4)$ become the two endpoints of a single statement parameterized by the number of faces $f$, with $f=1$ and $f=k$ respectively.","For a constant number of faces $f$, every such planar instance has an exact planar emulator of size $O(k^2)$, matching the known lower bound up to constants.","The emulator preserves distances inside each face through the one-face constructions and across faces through the central skeleton, so the full terminal metric survives in the compressed graph.","The size bound follows from giving each terminal $O(f)$ critical paths and noting that any pair of critical paths crosses at most once, yielding $O(f^2 k^2)$ total vertices.","The LP-feasibility route gives a way to certify exact emulator weights without a closed formula, which the paper suggests may apply to other distance-based graph problems."],"supporting_citations":[{"why":"It supplies the one-face exact planar emulator construction that the paper reuses for the terminals on each face.","marker":"[CO20]"},{"why":"It provides the companion one-face $O(k^2)$ emulator construction used inside each face.","marker":"[GHP20]"},{"why":"It establishes the general $O(k^4)$ upper bound and $\\Omega(k^2)$ lower bound that the new bound interpolates between.","marker":"[KNZ14]"},{"why":"It supplies the paths-and-intersections viewpoint and the LP-feasibility approach that this paper extends to $f$ faces.","marker":"[CT25]"},{"why":"It is the linear-programming duality lemma that turns infeasibility of the weight LP into the terminal-flow pair.","marker":"[Far98]"},{"why":"It is the planar flow-cut result used to reduce flow equivalence to cut equivalence in the Wye-Delta step.","marker":"[OS81]"},{"why":"It justifies the unique-shortest-path perturbation assumption used throughout the construction.","marker":"[EFL18]"}],"fun_headline_variants":["Exact planar emulators now O(f²k²) for k terminals on f faces","Planar distance emulators: exact and size O(f²k²)","From O(k⁴) to O(f²k²): exact planar emulators","Paths and intersections give exact O(f²k²) planar emulators","Unifying planar emulator bounds: exact O(f²k²)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument requires that locally rerouting a canonical path around a crossing never changes which terminal-flow demands are routable, so that a dominating flow in the skeleton can be carried back to the original graph; if any such rerouting changes routability, the linear-program feasibility proof for the edge weights collapses.","fun_headline_variants_meta":{"raw":{"variants":["Exact planar emulators now O(f²k²) for k terminals on f faces","Planar distance emulators: exact and size O(f²k²)","From O(k⁴) to O(f²k²): exact planar emulators","Paths and intersections give exact O(f²k²) planar emulators","Unifying planar emulator bounds: exact O(f²k²)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000948,"raw_usage":{"total_tokens":4034,"prompt_tokens":920,"completion_tokens":3114,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":536,"completion_tokens_details":{"reasoning_tokens":3012}},"tokens_in":536,"tokens_out":3114,"duration_ms":24845,"temperature":1.0,"reasoning_tokens":3012,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:53:19.476944+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the minimum cut separating $u$ from $\\{v,w\\}$ in the Y-shaped graph with edge capacities $c(x,u)$, $c(x,v)$, and $c(x,w)$. If that cut value is the smaller of $c(x,u)$ and $c(x,v)+c(x,w)$ rather than $c(x,u)$, then the claimed equality between the Y and $\\Delta$ cuts in the Wye-$\\Delta$ step fails, and the flow-morphing proof must supply a different local argument before the theorem's weight-setting lemma is established.","supporting_citations":[],"review_version":1}