{"id":"9b705de8-d591-4d08-87ce-f29c39d19479","arxiv_id":"2506.08585","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Sparse graph classes are first-order transducible from graphs on a fixed surface if and only if they admit a new type of bounded fan-crossing drawing on that surface.","lead":"This paper proves a new equivalence: a class of sparse graphs can be defined from graphs drawn on a fixed surface using first-order logic exactly when its graphs have certain restricted crossing drawings on that surface. The result gives a concrete geometric target for a long-open question about whether all toroidal graphs can be logically defined from planar graphs.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Forward direction of Theorem 3 rests entirely on Theorem 1 of arXiv:2505.15655, a recent overlapping-author preprint used without proof; if that characterization is wrong or has hidden hypotheses, the iff collapses even though the reverse direction is self-contained.","rationale":"The reader's conditional verdict is well calibrated: the reverse direction is a genuine self-contained contribution via Lemma 8, and the geometric constructions in Lemma 7 are plausible. The single load-bearing risk is the unproved external theorem, since the manuscript's main theorem is an equivalence and the forward direction cannot be established without it. The paper does disclose the dependence, which is good practice, but a careful reader should verify the theorem before relying on the characterization. This is not an internal inconsistency; it is an external correctness dependency, and the proposed concrete check would settle whether the concern actually lands.","tokens_in":14929,"tokens_out":25369,"duration_ms":324069,"concrete_test":"Verify Theorem 1 of arXiv:2505.15655 in the exact setting used here: take C to be the graphs embeddable in a fixed surface Sigma and D a weakly sparse class transducible from C. Concretely, re-derive the proof of Theorem 1 for C = planar graphs and check every step for hidden use of bounded expansion of C^* or of additional properties of D such as heredity, closure under disjoint unions, or copying transductions. In particular, confirm that the proof does not require C^* itself to be bounded expansion, since C^* fails this property: a star plus a universal vertex contains arbitrarily large cliques as depth-1 minors via model sets {u, leaf_i}. If Theorem 1 cannot be independently confirmed, the forward direction of Theorem 3 should remain conditional on the external characterization.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The only-if direction of Theorem 3 is exactly 'D transducible from C implies that every H in D has a monotone k-fold k-clustered fan-crossing drawing in Sigma after deleting at most k vertices.' Its proof is two sentences: apply Theorem 1 to get H' as a congestion-k depth-k minor of a graph in C^*, delete the at most k vertices whose model sets contain the universal vertex, then apply Lemma 7. Lemma 7 is proved in detail, but Theorem 1 is quoted from a recent preprint with overlapping authorship and is not proved, formalized, or even sketched here. The central equivalence therefore inherits the correctness of a nontrivial external theorem, including its exact hypotheses. This is not merely a citation issue: C^* is not itself a bounded-expansion class, since a large star plus a universal vertex already has arbitrarily large cliques as depth-1 minors, so one must check that the proof of Theorem 1 does not silently require bounded expansion of C^* or extra properties of D such as heredity or closure under disjoint unions. The paper's own footnote that the conference version omitted the 'monotone' condition also shows the definitional framework has shifted, so the forward proof's 'trivially monotone' claim in Lemma 7 would deserve a fuller argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces k-fold ℓ-clustered fan-crossing drawings in surfaces and proves Theorem 3: for a surface Σ, a weakly sparse graph class D is transducible from the class of graphs embeddable in Σ if and only if every H in D has a monotone k-fold k-clustered fan-crossing drawing in Σ after deleting at most k vertices. The forward direction combines Theorem 1 of Gajarský et al. (arXiv:2505.15655) with a minor-to-drawing lemma (Lemma 7). The reverse direction is proved constructively in Lemma 8 by encoding the drawing into an FO formula and an embedded colored graph. Corollary 4 gives a bounded-degree version with k-crossing drawings, and applications to 3D grids and toroidal graphs are discussed.","tokens_in":15085,"tokens_out":23569,"duration_ms":285938,"significance":"If Theorem 3 is correct, it is a significant bridge between FO transductions and graph drawing, giving a concrete topological obstruction for weak transducibility from surface-embeddable sources. The self-contained reverse direction with explicit FO formulas is a substantial contribution, and the 3D-grid non-k-planarity application is elegant. The main caveat is that the forward direction is not self-contained: it inherits an unproved, recent, overlapping-author characterization. The paper is transparent about this dependence, which makes the conditional value clear.","major_comments":[{"comment":"The only-if direction is exactly Theorem 1 of [13] followed by Lemma 7. Theorem 1 is a recent preprint with overlapping authorship and is neither proved nor sketched here. Because the characterization in Theorem 3 is an iff, the only-if direction collapses if Theorem 1 is false or has hypotheses not met. I request that the authors either include a proof or detailed proof sketch of the quoted theorem, or state the main theorem as conditional on [13] being accepted. In particular, verify explicitly that the theorem's hypotheses (C bounded expansion, D weakly sparse and transducible from C) are sufficient for the pointwise conclusion that D is contained in the congestion-k depth-k minors of C•, and that no extra assumptions on D such as heredity or closure under disjoint unions are used. The fact that C• is not itself bounded expansion makes this check non-vacuous.","section":"Section 3, proof of '⇒' of Theorem 3"},{"comment":"The proof concludes that the constructed O(k)-fold O(k)-clustered fan-crossing drawing is 'trivially monotone by our construction,' but the monotone condition in Definition 2 is load-bearing for Theorem 3, and the footnote notes that a previous version omitted it. Please provide the missing verification: for each edge f=vw, after placing a subdivision vertex at the meeting point b_f, every crossed edge on the v-side of b_f is assigned to the fan centered at v and every crossed edge on the w-side to the fan centered at w.","section":"Section 3, Lemma 7"},{"comment":"In the induction proving that an accepted path forces xy∈E(H), the step 'let j be such that F^i_j = F_x' needs justification. The formula's color condition only guarantees existence of some fan index j at component m_i; one must argue that the fan whose R/T side contains z_{4q} on the x-side of the component is exactly the fan centered at x. Please expand this step to make the induction sound.","section":"Section 3, Lemma 8(b), case (ii)"}],"minor_comments":[{"comment":"The bound 'at most k of the vertices m_i lie on P_xy' is justified by the k-fold subdivision of the original edge (at most k subsegments that carry crossings), not by the k-clustered condition as stated. Please correct the reason given.","section":"Section 3, Lemma 8(b), case (i)"},{"comment":"There is a typo 'ξ+k(x,y)' in the verification paragraph; it should be 'ξ_k(x,y)'.","section":"Section 3, Lemma 8(a)"},{"comment":"The assumption allows deleting at most ℓ edges, but the proof moves directly to an induced subgraph G'_1 obtained by deleting ≤ℓ vertices. This is fixable since G1 has maximum degree 3, but the short argument should be included.","section":"Section 4, Proposition 12"},{"comment":"The notation 'C' is used both for the source class of embeddable graphs and for the target class in the sentence 'If the considered class C is additionally of bounded maximum degree'; please clarify the notation.","section":"Section 1, abstract"},{"comment":"The phrase 'for some k'∈O(k)' should be reconciled with the integer quantifier in Theorem 3; since k is arbitrary this is fine, but the statement could explicitly say that k may be increased to absorb constants.","section":"Section 3, Lemma 7"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is conditional on arXiv:2505.15655; since one of the present authors (Jedelský) is also an author of that preprint, the editor may wish to check the overlap policy and ask the authors to confirm the status of [13]. The paper's own contribution (Lemma 8 and the drawing reformulation) is solid and would survive even if Theorem 3 were stated as conditional."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:2506.08585. The genuinely new thing is the drawing class they define and the two-way characterization in Theorem 3: for a surface Σ, a weakly sparse class D is transducible from Σ-embeddable graphs iff every graph in D has a monotone k-fold k-clustered fan-crossing drawing in Σ after deleting k vertices. That's a real bridge between logic and graph drawing, and it gives a clean new angle on the toroidal-graphs question. The reverse direction (Lemma 8) is self-contained and carefully proved, including the FO formula. Lemma 7's construction is explicit and plausible.\n\nThe main soft spot is the forward direction. It uses Theorem 1 from the Gajarský et al. preprint (arXiv:2505.15655) as a black box, and that paper has overlapping authorship and is not yet peer-reviewed. That dependency is genuine, but note the stress-test worry that C• is not bounded expansion does not land: Theorem 1 is applied to C (the surface-embeddable class, which is bounded expansion), and its conclusion is about C•. So that specific red flag is a false lead. The real issue is simply that the central iff inherits the correctness of a nontrivial external theorem. If that theorem is wrong, the forward direction fails; the reverse still stands. I'd want the referee to verify Theorem 1's proof or at least see a detailed sketch in an appendix.\n\nA second, minor issue: Lemma 7 says the constructed drawing is 'trivially monotone' and gives only a sentence. The monotone condition is subtle, and the proof would be more convincing with a few lines explaining the switch point along each edge. Also, the footnote about the conference version omitting 'monotone' is an honest disclosure, but it means the definition has been refined; the current version uses it consistently.\n\nThe 3D-grids corollary is known, but the authors openly say it is an illustration; the real meat is the equivalence itself.\n\nBottom line: this is a serious paper, the math is mostly explicit and the main theorem is a genuine new contribution. I'd send it to referees. I'd ask them to check the dependency on Theorem 1 and to ask the authors to expand the monotone argument. Despite the external dependency, I think it deserves review rather than a desk reject.","headline":"New equivalence between transducibility and fan-crossing drawings, with the forward direction leaning on a plausible but unproved recent theorem; worth refereeing but ask for a proof sketch of that dependency.","tokens_in":15711,"tokens_out":6016,"would_cite":true,"duration_ms":63151,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62","03C13","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A weakly sparse graph class is first-order transducible from the graphs embeddable in a fixed surface precisely when, for some fixed k, every graph in it has a monotone k-fold k-clustered fan-crossing drawing on that surface after…","keywords":["planar graphs","surface embeddings","k-planar drawings","fan-crossing drawings","first-order transductions","bounded expansion","weakly sparse graph classes","toroidal graphs"],"falsifier":"Find a weakly sparse graph class D that is FO-transducible from the planar graphs but provably is not contained, for any fixed k, in the class of congestion-k depth-k minors of planar graphs with a universal vertex added; that would refute the black-box theorem and hence the forward direction of the main characterization. One concrete route: show a bounded-degree class transducible from planar graphs whose members force more than k crossings on some edge in every planar drawing, even after deleting any k vertices or edges — a violation of Corollary 4 that would be directly observable from a drawing lower-bound proof.","tokens_in":14647,"feed_emoji":"✏️","tokens_out":9439,"duration_ms":102194,"temperature":0.7,"pith_summary":"First-order transductions are logical recipes that turn one graph class into another, and the paper asks which sparse target classes can be obtained this way from the graphs embeddable in a fixed surface. The answer it proposes is a purely geometric one: a weakly sparse class qualifies exactly when, for some fixed k, every graph in it can be drawn on that surface as a monotone k-fold k-clustered fan-crossing drawing after deleting at most k vertices. For bounded-degree targets, the condition simplifies to having a bounded number of crossings per edge, i.e., k-planarity in the plane. This two-way bridge turns logical non-definability proofs into drawing impossibility proofs and back, which the paper exploits to reprove that 3D-grids are not transducible from planar graphs and to give a concrete target for the open question of whether toroidal graphs are transducible from planar graphs.","feed_headline":"Bounded fan-crossing drawings equal transductions of surface graphs","feed_subtitle":"A new bridge lets drawing impossibility prove logical non-definability, and vice versa.","key_machinery":"One central object is the monotone k-fold k-clustered fan-crossing drawing: a drawing in which each edge may be subdivided by at most k−1 new vertices so that every connected component of the resulting crossing graph is covered by at most k extended fans (sets of subdivided edges all incident to one center vertex), with the monotonicity condition that along each original edge the fan assignment changes at most once, from the fan of one endpoint to the fan of the other. The companion machinery is the congested shallow minor: a minor model whose model sets have radius at most k and in which each host vertex belongs to at most k model sets. The proof that logical transductions imply such drawings (the forward direction) composes the black-box Theorem 1 — which places every weakly sparse transducible class inside bounded-congestion bounded-depth minors of the source class with a universal vertex added — with a lemma that converts any such minor model into the required fan-crossing drawing. The reverse direction constructs, for each fixed k, a first-order formula ξ_k and a colored surface embedding that recovers the original graph on the vertex set of the drawing, so that the drawing literally becomes the logical interpretation.","core_discovery":"The paper claims Theorem 3 as its central discovery: for any surface Σ, with C the class of graphs embeddable in Σ, a weakly sparse class D is FO-transducible from C if and only if for some fixed k every graph of D has a monotone k-fold k-clustered fan-crossing drawing in Σ after deleting at most k of its vertices. When D also has bounded maximum degree, this collapses to the simpler statement that D is transducible from C iff for some fixed k every graph of D has a k-crossing drawing in Σ after deleting at most k of its edges (Corollary 4). The authors prove the drawing-to-logic direction completely, by constructing a single first-order formula ξ_k plus a colored surface embedding that recovers each graph of D as an induced subgraph; the logic-to-drawing direction runs through the congested-minor characterization of transductions of bounded-expansion classes together with a lemma that turns any such minor model into the required fan-crossing drawing.","pith_inferences":["One extension not pursued in the paper: the bridge suggests a research program in which non-transducibility is shown by proving lower bounds on crossings per edge or on fan-cluster complexity, a concrete geometric task rather than a model-theoretic one.","The drawing-to-logic direction (Lemma 8) is unconditional: even if the black-box theorem on congested minors were to fail, any class admitting these bounded drawings for fixed k would still be weakly sparse transducible from the surface-embeddable graphs, so half of the characterization stands alone.","If the authors' closing conjecture is true — that every classical fan-crossing drawing is k-fold ℓ-clustered for small k and ℓ — then Theorem 3 would automatically extend to the classical fan-crossing setting, making the characterization much easier to apply.","For bounded-degree classes, Corollary 4 turns a logic question into a crossing-number question with a deletion-tolerance parameter; one could try to certify non-transducibility computationally for candidate classes by showing the minimal number of crossings per edge grows unboundedly even after deleting k edges."],"forward_implications":["The 3D-grid class is not k-planar for any fixed k, and more generally not k-crossing on any fixed surface (Corollary 9), so no fixed crossing budget can draw 3D grids on any surface.","Since 3D-grids fail the drawing condition, they are not FO-transducible from planar graphs, giving a third independent route to a result previously obtained by two other groups.","If there is any d ≥ 3 and ℓ for which every toroidal graph of maximum degree d is ℓ-planar after deleting at most ℓ edges, then every bounded-degree toroidal class is transducible from planar graphs (Proposition 12).","An affirmative answer to whether toroidal graphs are transducible from planar would force every toroidal graph to admit a monotone k-fold k-clustered fan-crossing drawing for some fixed k, which the authors consider unlikely and propose as a concrete attack on the problem."],"supporting_citations":[{"why":"The black-box characterization of weakly sparse transductions of bounded-expansion classes; it carries the forward direction of Theorem 3.","marker":"[13]"},{"why":"One of the two cited proofs that 3D-grids are not transducible from planar graphs, used alongside the new drawing argument for Corollary 9.","marker":"[14]"},{"why":"The other proof of non-transducibility of 3D-grids from planar graphs, via product structure.","marker":"[18]"},{"why":"Supplies the tree-width upper bound for k-planar graphs used to re-derive Corollary 9 by independent means.","marker":"[9]"},{"why":"Supplies the balanced-separator lower bound on 3D-grid tree-width used in that independent derivation.","marker":"[10]"},{"why":"Survey that frames the open toroidal-versus-planar transducibility question (Problem 10) which the drawing characterization targets.","marker":"[22]"}],"fun_headline_variants":["Fan-crossing bounds equal transductions on any surface","Drawing limits reveal logical definability of graph classes","Bounded fan-crossings: key to FO transductions on surfaces","3D grids case: drawing impossibility implies logical gaps","Surface graphs: a duality between drawings and logic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The forward half of the characterization depends on an unproved black-box theorem from a related preprint, namely that every weakly sparse class transducible from a bounded-expansion class sits inside its bounded-congestion, bounded-depth minors after adding a universal vertex; if that theorem carries hidden hypotheses or is wrong, the 'only if' direction fails even though the reverse direction is proved from scratch in this paper.","fun_headline_variants_meta":{"raw":{"variants":["Fan-crossing bounds equal transductions on any surface","Drawing limits reveal logical definability of graph classes","Bounded fan-crossings: key to FO transductions on surfaces","3D grids case: drawing impossibility implies logical gaps","Surface graphs: a duality between drawings and logic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000736,"raw_usage":{"total_tokens":3368,"prompt_tokens":1099,"completion_tokens":2269,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":715,"completion_tokens_details":{"reasoning_tokens":2200}},"tokens_in":715,"tokens_out":2269,"duration_ms":20161,"temperature":1.0,"reasoning_tokens":2200,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:08:18.509503+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a weakly sparse graph class D that is FO-transducible from the planar graphs but provably is not contained, for any fixed k, in the class of congestion-k depth-k minors of planar graphs with a universal vertex added; that would refute the black-box theorem and hence the forward direction of the main characterization. One concrete route: show a bounded-degree class transducible from planar graphs whose members force more than k crossings on some edge in every planar drawing, even after deleting any k vertices or edges — a violation of Corollary 4 that would be directly observable from a drawing lower-bound proof.","supporting_citations":[{"cited_title":"First-order transducibility among classes of sparse graphs","cited_arxiv_id":"2505.15655","evidence_quote":"The black-box characterization of weakly sparse transductions of bounded-expansion classes; it carries the forward direction of Theorem 3."}],"review_version":1}