{"id":"58348d91-17b0-4590-a2aa-8fc2df0bd442","arxiv_id":"1908.01426","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Swap Planarity, a puzzle where adjacent vertices swap locations, is NP-complete to solve, and minimizing swaps for trees is NP-complete, though any solvable instance needs only O(n-squared) swaps.","lead":"The authors introduce Swap Planarity, a puzzle game where players make a graph planar by swapping the positions of adjacent vertices, and prove complexity bounds for solving it. They show that some instances require quadratically many swaps, that solving general instances is NP-complete, and that even trees become NP-complete when minimizing the number of swaps.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 rests on an unproved clause-gadget lower bound: the 'It remains to argue' paragraph does not rule out a 5-swap solution for unsatisfied clauses, so the tree NP-completeness proof is not yet certified.","rationale":"The reader's weakest-assumption analysis points to exactly the gap I consider load-bearing: the informal lower-bound paragraph in Theorem 4. I agree that this prevents full certification of the tree NP-completeness result. I checked the other main ingredients: Theorem 3 follows from Cabello's fixed-point-set planar embeddability via the connected-graph realization argument; Lemma 1's sorting lower bound and Lemma 2's quadratic upper bound are standard and appear correct; the generation section is not central to the verdict. The recommended action is to fill in the clause-gadget lower bound with a rigorous case analysis or a formal proof, or at least to provide an exhaustive computer-verified check for the bounded gadget. Since this is an addressable gap rather than a demonstrated falsehood, conditional acceptance remains the appropriate verdict, and my independent read does not move it. Separately, I note that Theorem 9's Lemma 8 uses the assertion that a connected non-star graph has two disjoint edges, which fails for K3; mirror-image point sets are swap-equivalent for K3 yet have different order type, so that statement needs an additional exclusion, though it does not bear on the central NP-hardness claim.","tokens_in":12422,"tokens_out":17164,"duration_ms":186309,"concrete_test":"Implement the clause gadget of Fig. 7, including the final repetition of each of the three connection paths, as a straight-line embedded graph with O(1) vertices. For each of the eight truth assignments to the three incident variables, run a breadth-first search over all swap sequences of length at most 5, checking after each swap whether the drawing is plane. The gadget is finite and small, so this is computationally trivial. If any unsatisfied assignment (0, 2, or 3 true variables) reaches a plane drawing in 5 or fewer swaps, the claimed 5-versus-6 separation fails and Theorem 4's reduction collapses. If the search confirms the claimed bounds for all eight assignments, the gap is empirically closed, though a formal proof would still be needed for full certification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reduction in Theorem 4 is sound only if every unsatisfied clause requires at least six swaps while every satisfied clause can be untangled in five. The proof's only support for the lower bound is the paragraph beginning 'It remains to argue that there is no globally different set of swaps...'. That paragraph is an informal sketch, not a proof: it assumes that each crossing must be paid for by a dedicated nearby swap and that aligning the three surrounding triangle layers is the only way to clear the central crossings in few moves, but it does not rule out a single swap that moves an endpoint and simultaneously resolves several crossings in different layers, nor does it exclude sequences that share swaps between the clause gadget and the adjacent split or variable gadgets. The claim that swapping a triangle-layer vertex out costs at least two swaps per layer is asserted, not derived. Because the reduction's threshold k is set to five swaps per clause, any unsatisfied truth assignment that admits a five-swap solution would make the if-and-only-if fail. This is precisely the load-bearing claim flagged in the text itself as requiring further argument, and no formal case analysis or machine-checked proof is supplied.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Swap Planarity, a puzzle in which a move exchanges the positions of the two endpoints of an edge, and the goal is to reach a crossing-free straight-line drawing. It proves that some n-vertex instances require Ω(n²) swaps (Lemma 1), that any solvable instance can be solved in O(n²) swaps (Lemma 2), that deciding solvability is NP-complete for general graphs (Theorem 3), and that deciding whether a tree can be solved in at most k swaps is NP-complete (Theorem 4). The paper then proposes a five-step generator for puzzle instances with guarantees on visual separation, diversity, and absence of recognizable structure, reports experiments on point generation and convex-hull statistics, and characterizes swap-equivalence of two instances in terms of simultaneous graph isomorphism and order-type equivalence (Section 6).","tokens_in":12607,"tokens_out":14035,"duration_ms":142887,"significance":"If the proofs are completed, the paper's main algorithmic contribution is the NP-completeness of bounded-swap planarity for trees, which is a genuinely nontrivial contrast with the polynomial-time solvability of ordinary planarity for trees; the Ω(n²)/O(n²) bounds and the order-type characterization are also useful. The generation process and experiments are a practical contribution, and the paper is clearly written with reproducible constructions. Its central complexity claims are, however, conditional on the clause-gadget lower bound in Theorem 4, and the equivalence theorem needs a small domain correction.","major_comments":[{"comment":"The NP-hardness reduction for trees is not yet proven, because the lower bound for unsatisfied clauses is only sketched in the paragraph beginning 'It remains to argue that there is no globally different set of swaps...'. The text asserts that each crossing must be paid for by a dedicated nearby swap, that aligning the three triangle layers is the only way to clear the central crossings in few moves, and that swapping a triangle-layer vertex out costs at least two swaps per layer, but none of these assertions is derived. In particular, the argument does not rule out a swap that simultaneously resolves crossings in several layers, nor swaps shared between the clause gadget and the adjacent split or variable gadgets. Since the reduction's threshold is five swaps per clause, any unsatisfied assignment admitting a five-swap solution would invalidate the if-and-only-if. A complete case analysis (or a machine-checked enumeration of the gadget's swap sequences) is needed before Theorem 4 can be considered proved.","section":"§3, Theorem 4 (clause-gadget lower bound)"},{"comment":"The claim that every connected non-star graph has two edges with four distinct vertices is false: the triangle K3 is connected and not a star, but its edges pairwise share vertices. For K3, any two straight-line drawings on three non-collinear points are swap-equivalent under every vertex matching, because all three edges are mutually adjacent and no two edges can cross; however, the two point sets can have different order types (opposite orientations). This contradicts Theorem 9 as stated. The theorem needs an explicit exception for triangle graphs, or a hypothesis that the graph has at least four vertices (or matching number at least two).","section":"§6, Lemma 8 and Theorem 9"}],"minor_comments":[{"comment":"The total k for the reduction is not defined explicitly; the proof should state a concrete formula, for example k = B + 5m for a baseline B depending only on the variable and split structure, and should prove that B is independent of the truth assignment.","section":"§3, Theorem 4"},{"comment":"The step 'To construct a tree, we remove the middle edges from some basic constructions' should specify that the removed edges are chosen on cycles so that the graph remains connected; removing a bridge would produce a forest rather than a tree.","section":"§3, Theorem 4"},{"comment":"Lemma 2 is stated only for reaching a plane drawing, but Theorem 3 and Lemma 8 invoke the stronger fact that any target bijection can be realized in a connected graph; the lemma's proof actually establishes this stronger statement, so it should be stated explicitly.","section":"§3, Lemma 2 and Theorem 3"},{"comment":"Reference [19] misspells 'Theoretical Computer Science' as 'Theoretical Compututer Science'.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The tree NP-hardness proof is the main obstacle; I believe the claimed bound is plausible but the current text is not sufficient. The equivalence theorem's K3 gap is small and easily patched. I would not recommend acceptance before the clause-gadget case analysis is supplied."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a genuinely nice piece of puzzle-geometry work: it defines Swap Planarity, proves a clean Omega(n^2) lower bound, gives a straightforward NP-completeness reduction from fixed-point-set planar embedding, proves an O(n^2) upper bound via known token-swapping results, and characterizes puzzle equivalence in terms of order types. The generation experiments are described well enough to reproduce, and the writing is clear and honest about what is known versus what is new.\n\nWhat stands out as solid: Lemma 1 is rigorous and elegant; Theorem 3 follows correctly from Cabello's theorem; Section 6's equivalence result is properly proved and genuinely useful; the citation pattern is fair, crediting Yamanaka et al. and Mulzer-Rote where due. There are no fitted parameters, and the paper does not assume its own conclusions.\n\nThe soft spot is Theorem 4. The reduction's threshold is five swaps per clause, so the entire if-and-only-if depends on the claim that an unsatisfied clause requires at least six swaps. The only support for that claim is the paragraph beginning 'It remains to argue that there is no globally different set of swaps.' That paragraph is an informal sketch, not a proof. It asserts that each crossing must be paid for by a dedicated nearby swap and that aligning the triangle layers is the only cheap way, but it does not rule out a single swap that moves an endpoint and simultaneously clears crossings in several layers, nor does it exclude swaps shared between the clause gadget and adjacent split or variable gadgets. This is load-bearing, not a minor gap. The rest of Theorem 4—the gadget constructions and the correspondence between truth assignments and swap counts—is plausible, but the lower bound is the hard part and it is currently asserted rather than demonstrated.\n\nMinor concerns: no code or data is shipped for the generation experiments, and the claim that 'no puzzle instance cannot be generated' is stronger than what the experiments actually show. These are small; the main issue is the proof gap in Theorem 4.\n\nWho is this for? Graph drawing researchers, puzzle complexity people, and anyone designing abstract geometric games. The lower bound, the general NP-completeness reduction, and the equivalence theorem stand on their own regardless of Theorem 4. The paper deserves a serious referee. I would send it out, but I would tell the authors that Theorem 4's key lower-bound argument needs a complete case analysis or a formalized proof before the result can be accepted as certified.","headline":"Worth reading for the clean lower bound, the Cabello-based NP-completeness reduction, and the order-type equivalence theorem, but the tree NP-hardness proof has an unproved clause-gadget lower bound that is load-bearing.","tokens_in":13173,"tokens_out":4013,"would_cite":true,"duration_ms":46013,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","68Q17","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Deciding whether a sequence of vertex swaps can untangle a drawing is NP-complete, and for trees deciding whether k swaps suffice is NP-complete as well.","keywords":["Swap Planarity","graph drawing","NP-completeness","planar untangling","puzzle generation","order type","1-in-3-SAT","Delaunay triangulation"],"falsifier":"Enumerate all swap sequences of length at most five on the clause gadget with zero, two, or three true incoming variables; if any such sequence produces a plane drawing, the Theorem 4 reduction fails to separate satisfiable from unsatisfiable instances.","tokens_in":12208,"feed_emoji":"🧩","tokens_out":10840,"duration_ms":98650,"temperature":0.7,"pith_summary":"This paper introduces Swap Planarity, a puzzle in which each move swaps the locations of two vertices joined by an edge, and asks when swaps can turn a tangled drawing into a plane drawing. It shows that solving the puzzle is computationally hard: deciding whether any swap sequence reaches a plane drawing is NP-complete, and for trees, where a plane drawing always exists, deciding whether $k$ swaps suffice is also NP-complete. The paper also proves that a solvable instance never needs more than $O(n^2)$ swaps, that some one-crossing instances require $\\Omega(n^2)$ swaps, and that two connected non-star drawings are equivalent exactly when their graphs are isomorphic and their point sets share the same order type. It then describes a five-step generator that produces visually clear, varied puzzle instances and reports experiments on the trade-off between visual clarity and diversity.","feed_headline":"Untangling a swapped graph is NP-complete, even for trees","feed_subtitle":"A new puzzle game's optimal-solution problem stays hard on trees and needs a geometric generator for playable instances.","key_machinery":"The argument is carried by a gadget reduction from positive planar 1-in-3-SAT. Variable gadgets are long paths whose crossings are resolved by swapping either all even or all odd vertical edges, encoding false or true; split gadgets pass that value to a clause; and each clause gadget is designed so that exactly one true variable lets all crossings be removed in five swaps while zero or multiple true variables force at least six. For the upper bound, the paper uses a path-bubble argument in which swapping along a path between a misplaced vertex and its target position moves one token into place in $O(n)$ swaps, yielding $O(n^2)$ overall. A separate equivalence result identifies a drawing with another precisely when the underlying graphs are isomorphic and the point sets share the same order type, enabling an $O(n^3)$ equivalence test.","core_discovery":"The central discovery is that swap-based untangling is NP-complete even for trees: given an embedded tree and an integer $k$, asking whether $k$ swaps of edge endpoints can produce a plane drawing is NP-complete (Theorem 4). The proof reduces positive planar 1-in-3-SAT to the swap-count problem, wiring variable, split, and clause gadgets so that each satisfied clause can be untangled in five swaps while unsatisfied clauses require more. In addition, the paper proves that deciding solvability for general graphs is NP-complete (Theorem 3), that any solvable instance can be planarized with $O(n^2)$ swaps while some cycles with a single crossing require $\\Omega(n^2)$ swaps, and that two connected non-star drawings are swap-equivalent exactly when their graphs are isomorphic and their point sets have the same order type.","pith_inferences":["A corollary the paper does not spell out is that exact optimal play is out of reach for large instances, so practical generators must fall back on brute force for small swap counts or heuristics, the trade-off the experimental section measures.","The equivalence theorem suggests a natural distance measure for puzzle instances based on the size of the order-type matching that also preserves graph isomorphism, which could be used to diversify generated puzzles beyond the geometric indicators reported.","If the clause-gadget lower bound is correct, the same gadget family could probably be adapted to prove NP-completeness for other swap-restricted drawing variants, such as the rotation or stretch variants the paper lists but does not analyze."],"forward_implications":["Every solvable instance can be solved in $O(n^2)$ swaps, so the puzzle never demands unboundedly long solution sequences.","Some instances with only one edge crossing require $\\Omega(n^2)$ swaps, so a visually simple puzzle can hide a large search.","Because the general decision problem is NP-complete, no polynomial-time algorithm solves arbitrary instances unless P equals NP.","Because the tree version with a swap budget is NP-complete, optimal play is hard to automate even for the simplest graph class.","Swap-equivalence of two connected non-star drawings can be tested in $O(n^3)$ time, giving a concrete notion of instance diversity."],"supporting_citations":[{"why":"Supplies the NP-complete source problem, positive planar 1-in-3-SAT, that the tree reduction transforms.","marker":"[12]"},{"why":"Gives the NP-hardness of embedding a graph on a fixed point set, which Theorem 3 reduces to swap planarity.","marker":"[5]"},{"why":"Establishes that any assignment of connected-graph vertices to positions can be reached with $O(n^2)$ swaps, providing the polynomial upper bound.","marker":"[20]"},{"why":"Shows every tree can be embedded without crossings on any planar point set, so tree instances are always solvable.","marker":"[3]"},{"why":"Also supports tree embeddability on point sets, motivating the bounded-swap decision problem for trees.","marker":"[14]"},{"why":"Provides the $O(n^3)$ algorithm for enumerating order-type matchings used in the swap-equivalence test.","marker":"[10]"}],"fun_headline_variants":["Swap Planarity: NP-complete even on trees","Untangling swapped graphs is NP-complete, even for trees","Even trees resist swap untangling: NP-complete proof","Swap Planarity game proved NP-complete on trees","New puzzle: swap untangling is NP-complete, even for trees"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the claim that no clever alternative sequence of swaps can untangle the small arrangement that encodes a logical clause in fewer than six moves when the clause is unsatisfied; this is argued informally rather than proved exhaustively, and the NP-completeness reduction depends on it.","fun_headline_variants_meta":{"raw":{"variants":["Swap Planarity: NP-complete even on trees","Untangling swapped graphs is NP-complete, even for trees","Even trees resist swap untangling: NP-complete proof","Swap Planarity game proved NP-complete on trees","New puzzle: swap untangling is NP-complete, even for trees"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000724,"raw_usage":{"total_tokens":3164,"prompt_tokens":781,"completion_tokens":2383,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":397,"completion_tokens_details":{"reasoning_tokens":2300}},"tokens_in":397,"tokens_out":2383,"duration_ms":23613,"temperature":1.0,"reasoning_tokens":2300,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:13:50.182569+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all swap sequences of length at most five on the clause gadget with zero, two, or three true incoming variables; if any such sequence produces a plane drawing, the Theorem 4 reduction fails to separate satisfiable from unsatisfiable instances.","supporting_citations":[{"cited_title":"Minimum-weight triangulation is NP-hard","cited_arxiv_id":null,"evidence_quote":"Supplies the NP-complete source problem, positive planar 1-in-3-SAT, that the tree reduction transforms."},{"cited_title":"Planar embeddability of the vertices of a graph using a fixed point set is NP-hard","cited_arxiv_id":null,"evidence_quote":"Gives the NP-hardness of embedding a graph on a fixed point set, which Theorem 3 reduces to swap planarity."},{"cited_title":"Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno","cited_arxiv_id":null,"evidence_quote":"Establishes that any assignment of connected-graph vertices to positions can be reached with $O(n^2)$ swaps, providing the polynomial upper bound."},{"cited_title":"On embedding an outer-planar graph in a point set","cited_arxiv_id":null,"evidence_quote":"Shows every tree can be embedded without crossings on any planar point set, so tree instances are always solvable."},{"cited_title":"Embedding a planar triangulation with vertices at specified points","cited_arxiv_id":null,"evidence_quote":"Also supports tree embeddability on point sets, motivating the bounded-swap decision problem for trees."},{"cited_title":"Goodman and Richard Pollack","cited_arxiv_id":null,"evidence_quote":"Provides the $O(n^3)$ algorithm for enumerating order-type matchings used in the swap-equivalence test."}],"review_version":1}