{"id":"cc582d50-bf88-483e-ab7c-09edfe13b0e8","arxiv_id":"1908.08129","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Inserting a prescribed set of edges into a simple drawing is NP-complete, the maximization version is APX-hard, and one-edge insertion is polynomial when the endpoints form a dominating set.","lead":"This paper proves that deciding whether a given set of missing edges can be added to a simple drawing of a graph is NP-complete, and that maximizing the number of addable edges is APX-hard. It also gives a polynomial-time test for inserting a single edge when its endpoints dominate the graph.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The NP- and APX-hardness reductions rest on the unproved visual assertion that each gadget's uv edge can be inserted only in the marked regions; a single hidden insertion region would break the satisfiability equivalence.","rationale":"The paper is internally coherent, and the polynomial-time algorithm for the dominating-set case is supported by a real proof rather than by figures alone. The reader's CONDITIONAL verdict is appropriate. My concern is not that the gadget claims are false, but that they are the load-bearing unproved step: the NP-completeness and APX-hardness results are mathematically correct only if the drawn gadgets have no hidden insertion regions and if Lemma 2's blocking behavior is exact. The reader's weakest assumption identified the Section 2 gadget verification; I extend the same concern to the Section 3.1 vertex/edge gadgets, since a hidden insertion region there would break the independent-set correspondence. The wrong citation for monotone 3SAT is real but does not affect the mathematical argument. Because the paper's central claim is sound conditional on the visual gadget verification, and no independent verification is present in the text, the verdict remains CONDITIONAL rather than ACCEPT or REJECT.","tokens_in":17799,"tokens_out":10209,"duration_ms":111667,"concrete_test":"Represent each gadget from Fig. 2 as a planarized combinatorial map and enumerate all simple u-v arcs that avoid edges incident to u or v and cross every other edge at most once; verify that the feasible cells are exactly the dashed regions. Then repeat on the combined X-W-C drawing used in Lemma 2: insert u(X)v(X) in the false region, recompute the feasible cells for u(W)v(W); insert u(W)v(W) in each feasible cell and recompute the feasible cells for u(C)v(C). If any unplanned cell survives at any step, Lemma 2 fails. Run the same exhaustive check for the Fig. 4 vertex and edge gadgets and for both 180-degree rotations used in the reduction. The gadget sizes are small, so this enumeration is computationally trivial and would settle whether the obstruction is real.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reductions (Theorem 1 and Theorem 3/Corollary 5) depend on the local assertion made immediately after Fig. 2: 'In each of these three gadgets shown in Fig. 2, the edge uv can only be inserted in the regions where the dashed arcs are drawn,' and on the analogous sentence after Fig. 4 for the vertex and edge gadgets. No derivation of this 'only' claim is provided; the figures are the only evidence. The variable, clause, and wire gadgets are then combined rigidly in Lemma 2 and in the 2-page book drawing substitution, so an unplanned feasible insertion region in any one gadget would allow an insertion that does not correspond to a truth assignment, or would allow a clause edge to be inserted when Lemma 2 says it is blocked. The same unproved visual assertion is reused for the Section 3.1 gadgets, so the APX-hardness result inherits the same exposure. The citation to [4] for monotone 3SAT is indeed wrong and should be corrected, but that is an editorial issue; the load-bearing gap is the unverified gadget characterization.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational complexity of extending a simple drawing D(G) of a graph G by inserting a prescribed set M of missing edges. It claims three main results: deciding whether all edges of M can be inserted into D(G) is NP-complete (Theorem 1); maximizing the number of insertable edges is APX-hard (Theorem 3 and Corollary 5); and deciding insertability of a single edge uv is polynomial-time when {u,v} is a dominating set (Theorem 7). The hardness proofs reduce from monotone 3SAT and maximum independent set in cubic graphs using variable, clause, wire, vertex, and edge gadgets. The algorithmic part reformulates single-edge insertion as a 'path problem with holes' in the planar dual and gives a polynomial-time algorithm for instances with at most two holes.","tokens_in":17976,"tokens_out":8628,"duration_ms":81836,"significance":"If the results are correct, they settle the complexity of a natural graph-drawing extension problem and show a sharp contrast with the rectilinear and pseudolinear settings, where extension is trivial or always possible. The paper also provides a useful dual reformulation of single-edge insertion and a nontrivial polynomial-time case. The high-level strategy is coherent and the claimed reductions are plausible. However, the hardness results rest on gadget characterizations that are asserted visually rather than proved, and the proof of Lemma 4 relies on a 'routine to check' statement. These gaps are load-bearing and must be repaired before the theorems can be considered established.","major_comments":[{"comment":"The assertion that 'the edge uv can only be inserted in the regions where the dashed arcs are drawn' is not proved for any of the gadgets. The 'only' direction is essential: Lemma 2 and the satisfiability equivalence in Theorem 1, as well as the analogous equivalence in Section 3.1, require that no unmarked region can host uv. Because the rest of the reduction composes gadgets rigidly, a single additional feasible insertion region would permit insertions that do not correspond to a truth assignment or to an independent set, breaking the reductions. Please replace the visual assertion with a proof, for example by a case analysis of all possible positions of uv relative to the edges of each gadget, showing that every other placement forces uv to cross some edge more than once or to cross an edge incident to u or v.","section":"Section 2, after Fig. 2 and after Fig. 4"},{"comment":"The proof states that 'It is routine to check that it is a simple drawing' for the subdrawing induced by four vertex gadgets and the corresponding edge gadgets. This is not a proof, and this check is load-bearing for the APX-hardness reduction: Theorem 3 and Corollary 5 require D'(G') to be a simple drawing. The construction in items (i)--(vi) specifies where crossings with vertex-gadget edges occur, but it does not establish that two arcs from different edge gadgets cross at most once in all configurations, nor that the interaction between an edge gadget and the two vertex gadgets is exactly as in Fig. 4c. Please provide a detailed proof, for instance by analyzing the order of crossing points along each edge of each gadget and using the 1-page book order of the original graph.","section":"Section 3.1, proof of Lemma 4"},{"comment":"The claim that the decision problem is in NP 'since it can be described combinatorially' is not sufficient. A certificate for an extension must be specified: for example, one can give the planarization of D(G) together with the rotation system of the inserted edges, and the verifier must check simplicity in polynomial time. The input representation of the simple drawing D(G) also needs to be stated explicitly. Since NP-completeness comprises membership in NP, this gap should be closed by giving the certificate and the polynomial-time verification procedure.","section":"Section 2, first paragraph"},{"comment":"The proof of Lemma 2 is entirely visual: the cases are argued from Fig. 3 and depend on how the wire gadget is drawn around the variable and clause gadgets. The text does not prove that, in the false case, u(W)v(W) cannot be inserted in the yellow region because it would cross u(X)v(X) twice, nor that, in the true case, the yellow insertion can always be routed. Likewise, the statement that 'Since D(φ) is a 2-page book drawing, the constructed drawing D' is a simple drawing' is asserted without proving that all wire gadgets pairwise cross at most once, both locally around vertices and globally between gadgets. Please add formal lemmas for the wire routing and for the simplicity of the global construction.","section":"Section 2, Lemma 2 and construction of D'"}],"minor_comments":[{"comment":"Reference [4] is cited as the source for the NP-completeness of monotone 3SAT, but [4] is de Berg and Khosravi's paper on optimal binary space partitions, which does not support this statement. Please cite a correct reference for monotone 3SAT.","section":"References"},{"comment":"The paper contains duplicate figure numbers: Fig. 6 and Fig. 7 appear both in Section 4 and in Appendix C, and Fig. 8 appears once in Appendix B and once in Appendix C with different content. Please renumber the figures.","section":"Figures"},{"comment":"There are several typos and language errors: 'an slight abuse' should be 'a slight abuse'; 'Not that we can assume' should be 'Note that we can assume'; the proof of Lemma 4 contains 'such that such that'; and in the Conclusions, 'a pair u, v of non-adjacent edges' should be 'a pair u, v of non-adjacent vertices'.","section":"Throughout"},{"comment":"The statement 'It is easy to see' for the equivalence between a satisfying assignment and a heterochromatic path should be expanded. The correspondence is not immediate from the figure alone, especially because the variable subgraphs use the same color for the first edge of both the positive and negative paths; please explain how the path chooses exactly one literal per variable.","section":"Appendix B, proof of Theorem 6"},{"comment":"The proof of Lemma 7 refers to Fig. 8(a) and Fig. 8(b), but the cells F_p, F_q, and the arcs alpha and beta are not clearly labeled in the figures, which makes the case analysis hard to follow. Please add labels or a precise description of the cells used in the proof.","section":"Appendix C, Lemma 7"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is promising and the claimed results are likely correct, but the main risk is the unverified gadget characterization and the hand-waved simplicity checks. I recommend asking the authors to supply complete proofs for the 'only' insertion-region claims and for the simplicity of the global reductions before the hardness results are accepted. The incorrect citation for monotone 3SAT is an editorial issue but should also be fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper you asked about is Arroyo–Derka–Parada, \"Extending Simple Drawings\" (arXiv:1908.08129). It proves that deciding whether a given set of missing edges can be inserted into a simple drawing is NP-complete, that maximizing the number of insertable edges is APX-hard, and that the single-edge case is polynomial when the endpoints form a dominating set. The first two are new; prior work had the rectilinear and pseudolinear cases but not general simple drawings. The algorithmic part is a separate contribution, reducing one-edge insertion to a colored path problem in the dual with at most two holes and solving it in polynomial time. That section is genuinely interesting.\n\nWhere it is soft: the hardness reductions depend on gadget assertions, specifically the claim that 'the edge uv can only be inserted in the regions where the dashed arcs are drawn' (after Fig. 2 and after Fig. 4). This is stated without proof; the figures are the evidence. Lemma 2's proof is mostly a walk through Fig. 3. If any gadget has an unplanned insertion region, the equivalence between satisfiability and extendability breaks. I can't fully verify the figures from a text-only file, so I can't certify this, but this is a common style in computational geometry; still, a referee should ask for a more formal or coordinate-based verification, not just 'routine to check'. The stress-test note you sent lands on the right spot.\n\nSecond, the citation for monotone 3SAT is [4], which is de Berg and Khosravi on binary space partitions—clearly wrong. That should be fixed to a proper source. This is editorial, but it matters because the reduction source is load-bearing.\n\nThird, NP membership is hand-waved as 'can be described combinatorially'; the later dual-path characterization is a better witness and should be moved up. Also Appendix B has 'It is easy to see' for a 3SAT reduction; that is fixable in revision.\n\nThe central arguments otherwise hold together: the reductions are external (monotone 3SAT for set insertion, MIS for APX), no circularity, and the PPH algorithm has a structured proof. The paper is a credible contribution to graph drawing and topological graph theory. It deserves a serious referee; the main revisions are a correct citation, a more rigorous gadget verification, and tightening a few proof sketches.\n\nMy take: accept for peer review with revisions. The headline results are new and likely correct.","headline":"Genuinely new NP- and APX-hardness results for extending simple drawings, with the main caveat that the gadget claims rely on visual verification and one wrong citation; the paper deserves a serious referee.","tokens_in":18528,"tokens_out":2924,"would_cite":true,"duration_ms":28285,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68U05","05C10","05C62"],"pacs":[],"model":"deepseek-v4-flash","headline":"Extending a simple drawing by a prescribed set of missing edges is NP-complete, and maximizing the number of inserted edges is APX-hard.","keywords":["simple drawings","edge insertion","NP-completeness","APX-hardness","graph drawing","topological graphs","path problem with holes","dominating set"],"falsifier":"Take one of the three gadgets from Fig. 2, planarize the drawing by subdividing every crossing, and test each cell of the planarized arrangement to see whether the edge uv can be drawn inside that cell without crossing any existing edge more than once. If any unmarked cell admits such an insertion, the gadget assertion used in the reduction fails, and with it the if-and-only-if between insertability of M and satisfiability of the formula.","tokens_in":17574,"feed_emoji":"📐","tokens_out":10322,"duration_ms":94535,"temperature":0.7,"pith_summary":"Simple drawings are graph drawings in which any two edges meet at most once, either at a shared endpoint or at a proper crossing. The paper asks when a given simple drawing of a graph can be extended by adding a prescribed set of missing edges while keeping the drawing simple. Its main result is that deciding this is NP-complete, even though the analogous question is trivial for straight-line drawings and always possible for pseudolinear drawings (those whose edges can be extended to a pseudoline arrangement). The paper also proves that choosing the largest insertable subset is APX-hard, so no polynomial-time approximation scheme exists unless P=NP, and gives a polynomial-time algorithm for inserting a single edge when its endpoints dominate the graph. The upshot is that the simple-drawing extension problem is genuinely hard in general, with only special cases admitting efficient algorithms.","feed_headline":"Inserting missing edges into a simple drawing is NP-complete","feed_subtitle":"Even a single missing edge can be uninsertable; maximizing insertions is APX-hard, so no PTAS exists","key_machinery":"The load-bearing devices are three planar gadgets—the variable gadget, the clause gadget, and the wire gadget—each containing a special pair of vertices u,v whose missing edge uv has exactly one or two marked admissible insertion regions. In the NP-hardness proof, choosing the left or right region of a variable gadget records true or false; a wire gadget transmits this choice to a clause gadget and, when the literal is false, blocks the corresponding clause region by forcing any insertion to cross uv twice. For the polynomial-time single-edge result, the operative mechanism is different: the drawing is converted into a plane with at most two holes whose boundary traces the stars of u and v, and the existing edge segments become colored Jordan arcs; inserting uv is then equivalent to finding a pq-arc that crosses no color more than once. The algorithm solves this path problem with holes by enlarging holes along non-separating arcs and cutting through separating ones, reducing every relevant instance to one with a single hole.","core_discovery":"The central discovery is a dichotomy between easy drawing classes and arbitrary simple drawings. The paper proves that, given a simple drawing D(G) and a set M of missing edges, deciding whether M can be inserted into D(G) is NP-complete; the proof reduces monotone 3SAT to the extension problem by replacing variables, clauses, and incidences with planar gadgets whose only admissible insertion regions encode truth values and enforce clause satisfaction. Composing this with an approximation-preserving reduction from maximum independent set in cubic graphs yields that finding the largest subset of M that can be inserted is APX-hard, hence admits no polynomial-time approximation scheme unless P=NP. On the positive side, when exactly one edge uv is to be inserted and {u,v} is a dominating set (every other vertex is adjacent to u or v), the decision problem is solvable in polynomial time by reducing it to a path problem with at most two holes. These results place simple-drawing extension at a computational frontier: worst-case instances are intractable, but structured cases remain solvable.","pith_inferences":["The gadgets in the NP-hardness construction use pairwise disjoint vertex pairs for their uv edges, so the decision problem is NP-complete even when the candidate set M is a matching in the complement—a strengthening the paper does not state explicitly.","The single-edge algorithm's reduction to a path problem with at most two holes suggests that the difficulty of the still-open general single-edge problem may come from drawings whose planarization has many holes; testing bounded-hole classes would be a natural next step.","Because the reduction from maximum independent set is an L-reduction, any greedy or local-search insertion heuristic can be forced to be arbitrarily far from optimal on carefully drawn instances, so practical work would have to rely on structural restrictions or approximation schemes tailored to those restrictions."],"forward_implications":["No polynomial-time algorithm can decide insertability of an arbitrary prescribed set of missing edges, unless P=NP.","The maximization version admits no PTAS unless P=NP, so one cannot approximate the largest insertable subset to arbitrary precision in polynomial time.","A single missing edge can already be uninsertable, and examples exist in drawings of K6 minus one edge and in larger complete graphs minus one edge.","When the endpoints of the new edge form a dominating set, single-edge insertion can be decided in polynomial time.","The hardness is specific to simple drawings: the corresponding extension problems are trivial for rectilinear drawings and always solvable for pseudolinear drawings."],"supporting_citations":[{"why":"Paper's cited source for the NP-completeness of monotone 3SAT, the base problem of the reduction proving Theorem 1.","marker":"[4]"},{"why":"Shows a simple drawing in which the single edge uv cannot be inserted, motivating the extension problem and its hardness.","marker":"[15]"},{"why":"Establishes APX-hardness of maximum independent set on degree-3 graphs, the source problem for the maximization reduction.","marker":"[1]"},{"why":"Defines L-reductions and the approximation-preserving framework used to prove APX-hardness of the maximization version.","marker":"[19]"},{"why":"Supplies the independence lower bound used in Appendix A to verify the L-reduction parameters.","marker":"[23]"},{"why":"Alternative proof of the same independence bound, used alongside [23] in the L-reduction analysis.","marker":"[8]"},{"why":"Earlier work on saturated simple topological graphs that frames the question of when missing edges can be inserted.","marker":"[16]"}],"fun_headline_variants":["Inserting missing edges into simple drawings is NP-complete","Extending simple drawings is NP-complete; maximization is APX-hard","Simple-drawing extension: NP-hard for arbitrary edges, polynomial for dominating pairs","Maximizing inserted edges in simple drawings is APX-hard"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole reduction hinges on the assertion that in each gadget the edge uv can be inserted only in the marked regions, and that each wire gadget blocks its target clause region exactly as described; if a gadget admitted an unplanned insertion region, the equivalence between insertability and satisfiability would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Inserting missing edges into simple drawings is NP-complete","Extending simple drawings is NP-complete; maximization is APX-hard","Simple-drawing extension: NP-hard for arbitrary edges, polynomial for dominating pairs","Maximizing inserted edges in simple drawings is APX-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000391,"raw_usage":{"total_tokens":2040,"prompt_tokens":910,"completion_tokens":1130,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":526,"completion_tokens_details":{"reasoning_tokens":1054}},"tokens_in":526,"tokens_out":1130,"duration_ms":10389,"temperature":1.0,"reasoning_tokens":1054,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:48:56.585804+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take one of the three gadgets from Fig. 2, planarize the drawing by subdividing every crossing, and test each cell of the planarized arrangement to see whether the edge uv can be drawn inside that cell without crossing any existing edge more than once. If any unmarked cell admits such an insertion, the gadget assertion used in the reduction fails, and with it the if-and-only-if between insertability of M and satisfiability of the formula.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the independence lower bound used in Appendix A to verify the L-reduction parameters."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Alternative proof of the same independence bound, used alongside [23] in the L-reduction analysis."}],"review_version":1}