{"id":"9a6f1f38-2c32-49a1-9bb2-b992ea0958c5","arxiv_id":"2607.05362","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Forests, trees, and matchings can always be reconfigured on the torus and higher-genus orientable surfaces by rerouting one edge at a time while maintaining crossing-free embeddings.","lead":"This paper proves that crossing-free embeddings of forests (including matchings) on the torus can always be reconfigured into each other by rerouting one edge at a time. It matters for combinatorial reconfiguration and computational topology, extending prior work that only handled two-edge matchings on the torus.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The two-phase construction is sound, the key geometric observations (annulus neighborhoods on orientable surfaces, order preservation under orientation-preserving identifications) are correct, and limitations are transparently acknowledged.","rationale":"The reader correctly identified the geometric input model as the most visible assumption, but correctly assessed it as non-load-bearing for the existence claim. The central argument is a constructive two-phase algorithm with correct geometric foundations: annulus neighborhoods of simple closed curves on orientable surfaces (Phase 1), non-separating desire paths via boundary crossings (Phase 2), and careful management of detour interactions (Appendix A). The exponential dependence on k is acknowledged and conjectured to be tight (Open Problem 4). The negative results (Theorem 11) use a valid simulation argument via uniquely embeddable triangulations (Negami's theorem). The paper makes solid progress on an open problem from Ito et al. (TALG 2025). No adjustment to the ACCEPT verdict is warranted.","tokens_in":29740,"tokens_out":6352,"duration_ms":360922,"concrete_test":"Verify the nesting argument in Phase 2, Step 2 (Appendix A): construct a concrete example where a B* edge f has both a top loop detour (from Step 1b, crossing the left/right boundary) and needs a tree detour (from Step 2, around R*_x). Confirm that replacing the portion from p_L to p_R with the tree detour around R*_x does not introduce crossings with other B* edges that also have loop detours. Specifically, check that the tree detour, which goes counterclockwise around R*_x, does not intersect the left/right boundary detours of other edges that nest outside it. If even one such configuration produces a crossing, the nesting invariant fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the paper carefully looking for the weakest link in the central argument (Theorem 1). The argument has two phases: Phase 1 (Lemma 2) reconfigures to interior embeddings using frame trees, and Phase 2 (Lemmas 3–4) reconfigures between interior embeddings using the torus boundary. The key geometric claims are: (1) in Phase 1, the boundary of an ε-neighborhood of a frame tree (which is a tree, hence contractible) is a simple closed curve, so its neighborhood is an annulus, allowing parallel non-crossing rerouting; (2) in Phase 2, the ordering of raw ends near a_j and b_j is consistent because the surface is orientable, and the desire path ρ is non-separating because it crosses the top/bottom identification. Both claims are correct for orientable surfaces. The interaction between Step 1b detours (left/right boundary crossings) and Step 2 tree detours (around R*_x) is addressed in Appendix A through careful ordering and reversions, with a nesting argument that appears sound. The reader's concern about the geometric input model is a valid observation but is not load-bearing: the existence of a reconfiguration sequence is a topological statement that does not depend on the specific polyline representation, and the complexity bounds are clearly stated as representation-dependent, which is standard. The generalization to higher genus (Corollary 5) follows by choosing two pairs of identified sides, with the orientability condition ensuring order preservation. The paper is transparent about the failure on non-orientable surfaces (Open Problem 1). I do not identify a significant concern that would undermine the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","summary":"This paper studies the reconfiguration of crossing-free graph embeddings on surfaces, where vertices are fixed and edges are rerouted one at a time while maintaining a crossing-free embedding. The main result (Theorem 1) proves that for any forest with c components, any two embeddings on the torus can be reconfigured into each other, with a sequence length of O(c^3 k s^2) where s is the total number of polyline segments and k is the number of boundary-crossing segments. This extends to all orientable surfaces of genus g >= 1 (Corollary 5). The proof uses a two-phase approach: Phase 1 (Lemma 2) reconfigures both embeddings to interior embeddings via frame trees, and Phase 2 (Lemmas 3-4) reconfigures between interior embeddings using the torus boundary. The paper also provides sufficient conditions for reconfiguration on orientable surfaces for planar graphs with fixed rotation systems (Theorem 6) and series-parallel graphs (Theorem 7), results for perfect matchings in the projective plane (Theorem 8), and non-reconfigurability examples for general graphs (Theorem 11).","tokens_in":30047,"tokens_out":1581,"duration_ms":244203,"significance":"The main result resolves an open problem posed by Ito et al. [TALG 2025] by extending reconfigurability from 2-edge matchings on the torus to arbitrary forests on all orientable surfaces of genus >= 1. The two-phase construction (frame trees for Phase 1, desire paths for Phase 2) is a novel and clean technical contribution. The algorithmic results are constructive with explicit complexity bounds that are transparently representation-dependent. The paper also provides falsifiable negative examples (Theorem 11) and clearly delineates the boundary between positive and negative results in Table 1. The sufficient conditions for planar graphs with fixed rotation systems and series-parallel graphs further broaden the applicability. The generalization to the projective plane for matchings in a disk (Theorem 8) demonstrates the technique extends partially to non-orientable surfaces.","major_comments":[{"comment":"Lemma 3, Step 1b (p. 10-11): The nesting argument for top loop detours states that 'each successively rerouted curve will nest inside the previous ones, i.e., lie closer to d and closer to the top boundary.' This nesting is load-bearing for the claim that rerouted curves do not cross each other. However, the proof does not explicitly bound the number of nesting levels or argue that the epsilon-neighborhood has sufficient 'depth' to accommodate all crossings. Since the number of crossings along d_x can be as large as chi, and each nesting level requires additional space, a reader cannot verify from the text alone that the geometric construction does not self-intersect when chi is large. The appendix proof (Appendix A, p. 18-19) addresses the reuse of rho but does not revisit this geometric nesting bound. Please add a sentence or two clarifying why the nesting depth is not a geometrically载","section":null},{"comment":"Corollary 5 (p. 21): The complexity bound for genus g > 1 states the reconfiguration length is O(c^3 k g^2 s^2), but the proof argues that Phase 1 produces B* and R* with O(3^k * g * s) segments and chi = O(3^k * g^2 * s^2). Substituting into Lemma 4's bound of O(c(chi + s*)) gives O(c * (3^k * g^2 * s^2 + 3^k * g * s)) = O(c * 3^k * g^2 * s^2), which is O(c * 3^k * g^2 * s^2), not O(c^3 * k * g^2 * s^2) as stated. The factor of c^3 and k (vs 3^k) appear to come from the proof of Theorem 1 where chi is bounded by O(3^k s^2) with k = k(B)+k(R). Please verify that the stated bound in Corollary 5 correctly accounts for the substitution, or clarify the derivation.","section":null},{"comment":"Theorem 8 (p. 13-14): The proof constructs a canonical matching M where every curve passes through the crosscap exactly once, and then reconfigures B to M. The argument in Stage 1 (Claim 9) reduces intersections between curves in P and M_i. However, the proof of Claim 9 (Appendix D, p. 28-29) handles two cases, and in Case 2 uses a five-stage process involving the crosscap. The claim is that the number of intersections is reduced, but in intermediate stages 'the number of crossings may increase.' The proof should clarify that the intermediate embeddings remain crossing-free (i.e., that the curves in P remain pairwise disjoint throughout the five stages), since this is a requirement of the reconfiguration model.","section":null}],"minor_comments":[{"comment":"Section 3, p. 6, footnote 1: The discussion of epsilon being 'not constant' and numbered epsilon_1, epsilon_2, ... is somewhat unusual. Consider adding a brief remark that this is a standard cascading-neighborhood argument, or simply state that epsilon is chosen sufficiently small at each step.","section":null},{"comment":"Figure 2 (p. 6): The four panels are dense and the labels (a_j, b_j, etc.) are small. Consider enlarging or splitting into two figures for readability.","section":null},{"comment":"Lemma 2 (p. 5): The bound 'O(3^k)' on the reconfiguration sequence length should perhaps be 'O(3^k * k)' or clarified, since there are k steps and each step processes up to 3^{j-1} segments. The appendix (p. 18) states 'at most 3^j segments of B_j are reconfigured' in step j, and summation gives O(3^k), but a factor of k from the number of steps seems missing. Please verify.","section":null},{"comment":"Table 1 (p. 3): The entry for 'Perfect Matchings (inside disk)' under Non-Orientable references Theorem 8, but Theorem 8 is specifically about RP^2, not general non-orientable surfaces. Consider clarifying in the table that this is for the projective plane.","section":null},{"comment":"p. 7, line 3: 's1, ..., sk denote these k segments' — it would help to note that these are the boundary-crossing segments of B_0, not all segments of B.","section":null},{"comment":"The paper uses both 'Sigma-embedding' and 'bar-Sigma-embedding' notation. A brief reminder near Section 3 that bar-Sigma refers to the fundamental polygon representation would aid readers who skip to later sections.","section":null}],"recommendation":"major_revision","confidential_remarks":"The core construction is sound and the main positive result (Theorem 1) is correct in its essential argument. The major comments are about verification gaps in the geometric details (nesting depth in Lemma 3, intermediate crossing-freeness in Theorem 8) and a potential complexity bound discrepancy in Corollary 5. None of these appear to be fundamental errors — they seem fixable with additional exposition. I recommend major revision because at least two of these issues are load-bearing for the correctness of the algorithmic claims. The paper is a strong contribution once these gaps are addressed."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for a careful reading and for identifying three substantive points. All three comments are valid and require revision: (1) the nesting argument in Lemma 3 Step 1b needs an explicit geometric bound, (2) the complexity bound in Corollary 5 has a derivation error (the factor 3^k should appear instead of k), and (3) the proof of Claim 9 in Theorem 8 must clarify that intermediate embeddings remain crossing-free. We address each below.","responses":[{"response":"The referee is correct that the nesting argument is not sufficiently justified in the current text. We will add an explicit clarification. The key observation is that the nesting does not require geometrically distinct epsilon-neighborhoods of increasing depth. Rather, each successively rerouted curve detours to the left/right boundary of the fundamental square near the top, and the nesting is achieved by routing each subsequent detour in a thinner annular region between the previous detour and the curve d_x. Since the fundamental square boundary provides an unbounded (in the combinatorial sense) corridor along which parallel non-crossing polylines can be placed at arbitrarily small separation, the number of nesting levels is not constrained by any fixed geometric budget. Concretely, after the j-th rerouting, the (j+1)-th detour is placed in a strip of width epsilon_{j+1} < epsilon_j between the j-th detour and d_x, where the epsilon values form a decreasing sequence. This is the same mechanism used in Phase 1 (Lemma 2), where parallel polylines are placed in an epsilon-neighborhood of rho_j. We will add two sentences to Step 1b making this explicit: that the nesting is realized by a decreasing sequence of positive offsets, and that the corridor along the boundary of the fundamental square has sufficient room because the offsets can be chosen arbitrarily small. We note that this is consistent with the footnote on epsilon already present in the manuscript (p. 6), which acknowledges that epsilon is not a single constant but a sequence of suitably small values.","revision_made":"yes","referee_comment":"Lemma 3, Step 1b (p. 10-11): The nesting argument for top loop detours states that 'each successively rerouted curve will nest inside the previous ones, i.e., lie closer to d and closer to the top boundary.' This nesting is load-bearing for the claim that rerouted curves do not cross each other. However, the proof does not explicitly bound the number of nesting levels or argue that the epsilon-neighborhood has sufficient 'depth' to accommodate all crossings. Since the number of crossings along d_x can be as large as chi, and each nesting level requires additional space, a reader cannot verify from the text alone that the geometric construction does not self-intersect when chi is large. The appendix proof (Appendix A, p. 18-19) addresses the reuse of rho but does not revisit this geometric nesting bound. Please add a sentence or two clarifying why the nesting depth is not a geometrically."},{"response":"The referee has identified a genuine error in the stated bound of Corollary 5. The proof of Corollary 5 in Appendix A (p. 20-21) derives that Phase 1 produces s* = O(3^k * g * s) and chi = O(3^k * g^2 * s^2), and Phase 2 (via Lemma 4) gives a reconfiguration sequence of length O(c * (chi + s*)) = O(c * 3^k * g^2 * s^2). The correct bound is therefore O(c * 3^k * g^2 * s^2), not O(c^3 * k * g^2 * s^2). The erroneous factors of c^3 and k (in place of 3^k) appear to have been carried over from Theorem 1 without proper re-derivation. We note that in Theorem 1 itself, the bound O(c^3 * k * s^2) also appears to be incorrect: the proof of Theorem 1 substitutes chi = O(3^k * s^2) and s* = O(3^k * s) into Lemma 4's bound O(c * (chi + s*)), yielding O(c * 3^k * s^2), not O(c^3 * k * s^2). The factor c^3 may arise from the runtime bound O(c^3 * s* * (chi + s*)^2) of Lemma 4, but this is a runtime bound, not a sequence length bound. We will correct both Theorem 1 and Corollary 5 to state the bounds O(c * 3^k * s^2) and O(c * 3^k * g^2 * s^2) respectively for the sequence length, and verify that the segment counts and runtime bounds are similarly consistent.","revision_made":"yes","referee_comment":"Corollary 5 (p. 21): The complexity bound for genus g > 1 states the reconfiguration length is O(c^3 k g^2 s^2), but the proof argues that Phase 1 produces B* and R* with O(3^k * g * s) segments and chi = O(3^k * g^2 * s^2). Substituting into Lemma 4's bound of O(c(chi + s*)) gives O(c * (3^k * g^2 * s^2 + 3^k * g * s)) = O(c * 3^k * g^2 * s^2), which is O(c * 3^k * g^2 * s^2), not O(c^3 * k * g^2 * s^2) as stated. The factor of c^3 and k (vs 3^k) appear to come from the proof of Theorem 1 where chi is bounded by O(3^k s^2) with k = k(B)+k(R). Please verify that the stated bound in Corollary 5 correctly accounts for the substitution, or clarify the derivation."},{"response":"The referee is correct that this needs clarification. The proof of Claim 9 in Appendix D describes modifications to the curves in P = {P_i, ..., P_n} and notes that 'the number of crossings between {P_i, ..., P_n} and M_i may increase in intermediate steps.' This refers to crossings between the P-curves and M_i, not crossings among the P-curves themselves. However, the proof does not explicitly state that the curves in P remain pairwise disjoint throughout the five stages, which is indeed a requirement of the reconfiguration model. We have verified that pairwise disjointness is maintained: in each stage, the modifications replace arcs of individual curves with new arcs that closely follow M_i, previously redrawn arcs, or the boundary of the thickening N_i, and these new arcs are routed in sufficiently small neighborhoods that are chosen to be disjoint from all other curves. Specifically, in Step 1, each gamma'_ell closely follows M_i and the previously redrawn arcs in a nested fashion (analogous to the nesting in Lemma 3); in Step 2, each new arc closely follows the union of M_i and the Stage 1 arcs, again in a nested fashion; in Steps 4 and 5, the reversions follow the boundary of N_i. We will add a sentence after the description of the five stages stating explicitly that throughout all stages, the curves in P remain pairwise disjoint because each new arc is routed in a sufficiently small neighborhood that avoids all other curves, and that each stage consists of valid reconfiguration moves (one edge rerouted at a time).","revision_made":"yes","referee_comment":"Theorem 8 (p. 13-14): The proof constructs a canonical matching M where every curve passes through the crosscap exactly once, and then reconfigures B to M. The argument in Stage 1 (Claim 9) reduces intersections between curves in P and M_i. However, the proof of Claim 9 (Appendix D, p. 28-29) handles two cases, and in Case 2 uses a five-stage process involving the crosscap. The claim is that the number of intersections is reduced, but in intermediate stages 'the number of crossings may increase.' The proof should clarify that the intermediate embeddings remain crossing-free (i.e., that the curves in P remain pairwise disjoint throughout the five stages), since this is a requirement of the reconfiguration model."}],"tokens_in":30023,"tokens_out":1826,"duration_ms":224278,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"This paper resolves the natural open problem left by Ito et al.: forests (including matchings of arbitrary size) are always reconfigurable on the torus and higher-genus orientable surfaces. That is a genuine new result. The two-phase construction is the right approach — Phase 1 uses frame trees to pull everything into the interior of the fundamental polygon, Phase 2 uses the torus boundary via desire paths to reconfigure between interior embeddings. Both phases are constructive with explicit complexity bounds, and the generalization to genus g ≥ 1 is straightforward once the torus case is settled. The negative results (Theorem 11) using uniquely embeddable triangulations via Negami's theorem are a nice touch — they cleanly delineate where reconfiguration fails and why. The results for planar graphs with fixed rotation systems and for series-parallel graphs round out the picture well. The projective plane result (Theorem 8) is a reasonable partial step toward the non-orientable case. The proofs in the appendices are detailed, including the complexity analysis and the key optimization in Appendix A where the same desire path is reused across steps to keep the sequence length polynomial in the crossing number. The nesting arguments for the detours in Steps 1b and 2 are handled carefully. On the soft spots: the exponential dependence on k (the number of boundary-crossing segments) in Phase 1 is real but the authors are transparent about it and conjecture a matching lower bound. The geometric input model — polylines where each segment crosses the boundary at most once — is a restriction, but the existence of a reconfiguration sequence is a topological statement that does not depend on the representation, and the complexity bounds are clearly flagged as representation-dependent. This is standard for the setting. The non-orientable case is left open, which is honest — the order-preservation argument in Phase 2 genuinely breaks down for orientation-reversing identifications, and the authors explain why. I agree with the reader and the stress-test that there is no load-bearing flaw. The paper deserves a serious referee. It would benefit from a careful check of the nesting/reversion arguments in Appendix A, since those are the most intricate part of the construction, but I see no reason to doubt them on a first reading.","headline":"Solid paper resolving the Ito et al. open problem on forest reconfiguration on the torus. The two-phase construction works, the negative results are clean, and the boundary between positive and negative results is well-drawn.","tokens_in":30577,"tokens_out":1007,"would_cite":true,"duration_ms":115736,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["02.40.-k","02.40.Pc","02.10.Ox"],"model":"glm-5.2","headline":"Forests always reconfigure on the torus","keywords":[],"falsifier":"If one could exhibit two embeddings of a forest on the torus where every possible single-edge rerouting sequence necessarily passes through a crossing configuration, the main theorem would fail. More concretely, a pair of forest embeddings on the torus that are provably not reconfigurable would contradict Theorem 1.","tokens_in":29874,"feed_emoji":"🔄","tokens_out":671,"duration_ms":175610,"temperature":0.7,"pith_summary":"This paper proves that any two crossing-free embeddings of a forest on a torus can be reconfigured into each other by rerouting one edge at a time while keeping all intermediate embeddings crossing-free. The result extends to every orientable surface of genus at least one. The authors give a constructive two-phase algorithm: Phase 1 reroutes all edge curves away from the boundary of a fundamental polygon representation using a sequence of auxiliary spanning trees called frame trees, and Phase 2 exploits the torus topology—specifically the ability to route curves around the identified boundary—to systematically eliminate crossings between the two embeddings. The reconfiguration sequence length is O(c^3 k s^2) where c is the number of connected components, s is the total number of polyline segments, and k is the number of boundary-crossing segments. Beyond forests, the paper shows that planar graphs with a fixed rotation system and series-parallel graphs are also always reconfigurable on orientable surfaces of genus at least one, provides sufficient conditions for reconfiguration in the projective plane, and proves that for general graphs reconfiguration is not always possible.","feed_headline":"Forests always reconfigure on the torus","feed_subtitle":"Any two crossing-free embeddings of a forest on a genus-one surface can be transformed into each other one edge at a time, and the result","key_machinery":"Frame trees (auxiliary Steiner trees used in Phase 1 to progressively eliminate boundary crossings), desire paths (curves that hug the target embedding and cross the boundary once, used in Phase 2 to guide rerouting), and the fundamental polygon representation of the surface.","core_discovery":"The central discovery is that the topological freedom provided by any positive genus—specifically, the ability to route curves around the boundary of a fundamental polygon—suffices to guarantee reconfigurability for forests, and this extends to several broader graph classes. The key mechanism is a two-phase reduction: first eliminate all boundary crossings using frame trees (auxiliary Steiner trees that gradually absorb boundary-crossing segments), then use the now-clean boundary as a corridor to reroute edges one at a time past fixed subtrees. The torus provides just enough room to route a desire path that wraps around the boundary once, creating a non-separating curve that allows parallel弧","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Frame trees unlock crossing-free rerouting on the torus","Reconfiguring crossing-free forest embeddings on orientable surfaces","Forest embeddings always reconfigure on positive-genus surfaces","A two-phase method for rerouting curves on surfaces","How topological freedom enables edge rerouting on the torus"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The algorithm assumes a specific geometric input model where each edge is a polyline whose individual segments cross the fundamental polygon boundary at most once. The complexity bounds depend on the number of such boundary-crossing segments k, which is a property of this particular representation rather than an intrinsic property of the graph or surface. While the authors argue arbitrary embeddings can be converted to this form, the exponential dependence on k means the cost","fun_headline_variants_meta":{"raw":{"variants":["Frame trees unlock crossing-free rerouting on the torus","Reconfiguring crossing-free forest embeddings on orientable surfaces","Forest embeddings always reconfigure on positive-genus surfaces","A two-phase method for rerouting curves on surfaces","How topological freedom enables edge rerouting on the torus","Eliminating boundary crossings to reroute graph embeddings"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":1009,"prompt_tokens":515,"completion_tokens":494,"prompt_tokens_details":null},"tokens_in":515,"tokens_out":494,"duration_ms":31131,"temperature":1.0,"reasoning_tokens":441,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-07T14:39:09.980468+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"If one could exhibit two embeddings of a forest on the torus where every possible single-edge rerouting sequence necessarily passes through a crossing configuration, the main theorem would fail. More concretely, a pair of forest embeddings on the torus that are provably not reconfigurable would contradict Theorem 1.","supporting_citations":[],"review_version":1}