{"id":"6321423d-ac36-49a3-9547-4352b11f1b7e","arxiv_id":"1908.06504","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A graph that can be drawn with every edge angle above 60 degrees has at most 2n−6 edges, apart from explicitly listed small exceptions, and deciding if such a drawing exists is NP-hard.","lead":"This paper studies graph drawings in which every pair of edges, whether adjacent or crossing, meets at an angle above 60 degrees. It proves such drawings have at most 2n−6 edges for n vertices, except for a few small cases, and that deciding whether such a drawing exists is NP-hard.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The NP-hardness reduction depends on an unproved uniqueness/rigidity claim for 60° gadget embeddings; without a proof that the frame has a unique straight layout, the binary variable-orientation argument and Theorem 2 do not follow.","rationale":"The reader's conditional verdict is exactly right. The upper-bound theorem is supported by a finite case analysis with explicit exceptions, a disconnected-graph lemma, and a separate argument for replacing vertices by crossings; that part is not where I see a hole. The NP-hardness proof, however, is the central second claim and it is not self-contained: the entire construction hangs on the sentence in Appendix E that the frame embedding is unique up to similarity. The text never proves rigidity, and the observation that triangles are equilateral is insufficient because equilateral constraints are angle constraints and leave room for triangular-lattice bends and different local scales unless edge-sharing propagates a single scale. My disagreement is not with the conclusion but with the missing certificate. A concrete enumeration check for the smallest instance would show whether the claimed rigidity is true or false; until then Theorem 2 should be treated as conditional, which matches the reader's verdict.","tokens_in":10243,"tokens_out":16377,"duration_ms":188987,"concrete_test":"Instantiate the reduction with a tiny formula, e.g., n=m=1, and construct the graph as in Fig. 2(b). Encode a candidate drawing by coordinates of every vertex with constraints: every 3-cycle is equilateral, and every angle between incident or crossing edges is at least 60°. Use an exact/interval constraint solver or a numerical optimizer with many random restarts to enumerate all solutions up to similarity. If any solution has a bottom or top path that is not the straight alternating strip of Fig. 2(b) (for instance, a 120° bend), the uniqueness assertion in Appendix E is false and Theorem 2 needs a new reduction. If exhaustive search for this small instance finds only the intended configuration, the concern is weakened, though the check should then be repeated for the full-sized frame.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing point is the unproved uniqueness/rigidity assertion in Section 3 and Appendix E. The reduction requires that every TAR=60 drawing of the frame, variable gadget, connector gadget, and clause gadget is unique up to rotation, scaling, and reflection, and that variable gadgets are forced to lie vertically between Xi and Xi' with a binary left/right orientation. This is asserted ('As an embedding ... again is unique') but not derived. The observation that every 3-cycle in such a drawing is equilateral is only an angle constraint; it does not by itself imply a straight bottom/top path or a unique global layout. A strip of edge-adjacent equilateral triangles can, for example, be laid out along directions 0°, 120°, 0°, 120° while all vertex gaps remain 60°, so the 'straight path' and the slope-60° lines ℓ1 and ℓ2 need a rigorous argument. If any non-congruent embedding exists, a variable gadget need not point consistently right/left, and the contradiction argument for a horizontal clause-literal path landing on a left literal fails. Since the satisfiability direction depends on this binary orientation, Theorem 2 is not established by the text as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the total angular resolution TAR(G), defined as the largest over straight-line drawings of the minimum angle between any two edges that are incident or cross. Theorem 1 states that, apart from a finite list of constant-size exceptions, any n-vertex m-edge graph with TAR(G) > 60° has m ≤ 2n − 6, and claims this bound is tight. Theorem 2 claims that deciding whether a graph has TAR(G) ≥ 60° is NP-hard. The proof of Theorem 1 proceeds by planarizing a drawing and combining Euler's formula with angle-counting lemmas (Lemmas 1–3, Observation 1, and the disconnected case in Appendix D). The NP-hardness proof in Section 3 and Appendix E builds equilateral-triangle gadgets and a triangular frame, asserts that all 60° embeddings of these gadgets and of the frame are unique up to rotation, scaling, and reflection, and then extracts a satisfying truth assignment from the resulting literal orientations.","tokens_in":10477,"tokens_out":15710,"duration_ms":167856,"significance":"If Theorem 1 is correct, it is a clean extremal result for graph drawing: it gives an exact maximum edge count for graphs admitting drawings whose smallest vertex/crossing angle exceeds 60°, and the claimed tightness makes the bound sharp. The proof is self-contained and elementary, with no fitted parameters and no circular dependence on prior results of the authors. The claimed NP-hardness would also resolve the computational status of the 60° recognition problem. However, the manuscript as submitted does not fully support Theorem 2, and the 90°/120° bounds announced in the conclusion are unsupported. The significance is therefore conditional on completing those proofs.","major_comments":[{"comment":"The proof of Theorem 2 rests on the assertions that every TAR = 60° embedding of the clause gadget, the variable gadget, the connector gadget, and of the whole frame is unique up to rotation, scaling, and reflection. This is not proved anywhere. TAR ≥ 60° only forces each triangular face to be equilateral; it does not by itself force strips of edge-adjacent equilateral triangles to be straight, since such a chain can be folded at a shared edge while all incident angles remain 60° or 120°. Consequently, the claims that the bottom/top paths are straight, that the lines ℓ1 and ℓ2 have slope ±60°, and that each variable gadget has a binary left/right orientation are unsupported. The satisfiability direction of the reduction depends on exactly that binary orientation, so Theorem 2 is not established as written.","section":"Section 3 / Appendix E"},{"comment":"The sentence 'In addition we have been able to obtain similar bounds for graphs with TAR(G) ≥ 90° and TAR(G) > 120°' announces bounds m ≤ 2n − 2√n and m ≤ n with no proof and no appendix. No argument is supplied for these statements, yet the open problem at the end of the section refers to them. These claims should either be proved or explicitly labeled as conjectures; as written, the paper asserts results it does not support.","section":"Section 4, Conclusion"},{"comment":"The step 'All eight inner angles of the drawing, which are incident to the convex hull have more than 60°. This implies ∠BAC + ∠ABC ≤ 60°' is not justified. The fact that the inner angles of the pentagon sum to 540° does not, by itself, force such a bound on the sum of two subangles at the hull vertices. Since Lemma 4 is used in Theorem 1 to rule out crossing versions of the planarization exceptions, this step needs a complete angle-accounting or a different argument.","section":"Appendix C, Lemma 4"}],"minor_comments":[{"comment":"The text 'As an embedding with total angular resolution 60° of this frame again is again unique' contains a duplicated 'again'; please fix the typo.","section":"Section 3"},{"comment":"The sentence 'Applying Lemma 1 to every component gives m ≤ 2m − 6' should read m ≤ 2n − 6; as typeset the inequality is nonsensical.","section":"Theorem 1 proof"},{"comment":"The tightness claim is asserted rather than proved: the layered 8-gon in Fig. 1(b) is stated to have TAR > 60° and to generalize to n = 8k, with details deferred to a full version. Please include the argument or an explicit reference to a publicly available version.","section":"Section 2"},{"comment":"The computation 'm = 2 · 4 − 6 = 2' is confusingly written; the conclusion is correct, but the sentence should be clarified.","section":"Appendix D, Lemma 5"}],"recommendation":"major_revision","confidential_remarks":"The edge-bound part of the paper is promising and appears to be in good shape, but the NP-hardness proof is missing a central rigidity argument, and the conclusion announces additional bounds without proof. I would ask the editor to require the authors to supply a complete proof of the uniqueness/rigidity claim (or a different reduction) and to either prove or remove the 90°/120° statements before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result—m ≤ 2n−6 for graphs with TAR > 60°, up to a finite list of constant-size exceptions—is a solid piece of extremal graph drawing. The proof via planarization and Euler's formula is checkable, and the tightness construction makes the bound sharp. That alone is worth a serious look.\n\nThe NP-hardness part is where the paper goes soft. Theorem 2 rests on the claim that every TAR=60 embedding of the frame and gadgets is unique up to rotation, scaling, and reflection. That is asserted in Section 3 and again in Appendix E, but never proved. The stress-test note has it right: a strip of edge-adjacent equilateral triangles is not necessarily straight. Flip one triangle across a shared edge and you get a zigzag that still respects 60° at every vertex. So the 'straight bottom path' and the lines ℓ1 and ℓ2 are not forced by the angle condition. Without that rigidity, the binary left/right orientation of the variable gadgets doesn't follow, and the satisfiability direction collapses. That is a genuine hole, not a nitpick.\n\nAlso, the conclusion announces upper bounds for TAR ≥ 90° (m ≤ 2n−2√n) and TAR > 120° (m ≤ n) without proof. Those are presented as results, not conjectures. They may be true, but as written they're unsupported. At minimum they need a proof or an explicit 'full version' pointer.\n\nIf I were editor, I'd send it to referees. The extremal bound is a real advance and the proof is mostly rigorous; the NP-hardness claim is interesting but currently unproven. I'd cite the 2n−6 result, and I'd want to see a proof of Theorem 2 before trusting it. This is a serious paper with a clear, checkable main proof; the gap is a missing rigidity argument, not a hand-wave. Bring it to reading group if you want to discuss what makes a reduction brittle.","headline":"The 2n−6 extremal bound is solid and checkable; the NP-hardness proof rests on an unproved—quite possibly false—rigidity claim.","tokens_in":11043,"tokens_out":3794,"would_cite":true,"duration_ms":33309,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62","68Q17","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Graphs with total angular resolution above 60 degrees have at most 2n−6 edges, except for a short list of small exceptions, and the bound is tight.","keywords":["total angular resolution","angular resolution","crossing resolution","graph drawing","NP-hardness","extremal graph theory","planar graph","60-degree threshold"],"falsifier":"Search for a continuous family of drawings of the connector gadget (two triangles sharing an edge) in which all angles stay at least 60° but the distance between the two outer vertices changes; finding such a flex would invalidate the rigidity claim and break the NP-hardness reduction. For the edge bound, exhibit any graph outside the listed exceptions with TAR(G)>60° and more than 2n−6 edges; even one example would refute Theorem 1.","tokens_in":10032,"feed_emoji":"📐","tokens_out":9013,"duration_ms":79367,"temperature":0.7,"pith_summary":"Any graph that can be drawn so that every pair of edges—whether they meet at a vertex or cross—form an angle larger than 60 degrees can have at most 2n−6 edges, apart from a short list of small exceptional drawings. That bound is tight: infinitely many graphs attain it while keeping all angles above 60 degrees. The same 60-degree threshold is also computationally sharp, since deciding whether a graph admits such a drawing with exactly 60 degrees is NP-hard. The paper thus settles the extremal edge count at the 60-degree resolution threshold and shows that recognizing graphs meeting that threshold is as hard as solving 3SAT.","feed_headline":"Graphs with over-60° angles have at most 2n−6 edges","feed_subtitle":"The edge bound is tight, and deciding whether a graph can be drawn with 60° resolution is NP-hard.","key_machinery":"The proof rests on planarization: each crossing becomes a vertex, turning the drawing into a planar map whose face sizes are controlled by the 60° angle condition. Lemma 1 bounds the number of edges by 2n−2−⌈k/2⌉ in terms of the size k of the unbounded cell, and Observation 1 uses the angle sum of a simple polygon to limit how many edges can hang inside an outer face. Careful case analysis over the size of the unbounded cell (4, 5, 6, or at least 7) yields Lemma 3 and then Theorem 1. For the NP-hardness direction, the machinery is a family of triangle-based gadgets—clause, variable, and connector gadgets—whose embeddings with total angular resolution exactly 60° are asserted to be unique up to rotation, scaling, and reflection; these are assembled into a rigid triangular frame, and the lines ℓ1 and ℓ2 through the frame force horizontal clause-to-literal paths to end on the 'true' side of a variable gadget, encoding a satisfying assignment.","core_discovery":"The paper proves a tight extremal bound at the 60° threshold of total angular resolution. For every graph G with n≥3 vertices and m edges, if TAR(G)>60° then either G is one of ten explicitly listed constant-size exceptions or m≤2n−6. Examples constructed by nesting 8-gons show equality m=2n−6 is achieved for infinitely many n, so the bound cannot be improved. The proof proceeds by planarizing a drawing (replacing each crossing by a vertex) and applying Euler's formula together with an angle-sum argument that bounds the number of interior edges incident to the outer face. As a second result, the paper shows NP-hardness of deciding whether TAR(G)≥60°, by reducing 3SAT to the existence of a drawing built from equilateral-triangle gadgets whose 60° embeddings are rigid.","pith_inferences":["Because the NP-hardness gadgets stay rigid only at exactly 60°, a natural testable extension is whether the reduction can be modified to show hardness for every angle in (60°, 90°], which would move the hardness threshold upward toward the easy 120° regime.","The extremal drawings in the tightness construction are nested 8-gons with two interior edges; a plausible conjecture is that every extremal graph with m=2n−6 and TAR>60° belongs to a similarly structured family, which could be checked by extending the case analysis.","The near-planar edge count suggests that graphs drawn with TAR>60° have bounded crossing number in a quantitative sense; one could test whether the planarization used in the proof preserves enough structure to bound the number of crossings by a constant times n.","Combining the two theorems, the class TAR>60° is simultaneously sparse and hard to recognize; this makes it an interesting testbed for approximation algorithms that aim to draw graphs close to the 60° threshold."],"forward_implications":["Graphs with total angular resolution above 60° are sparse: their edge count cannot exceed 2n−6, the same number as a maximal planar graph, so such drawings are in a precise sense almost planar.","The bound is best possible: for every sufficiently large n there exist graphs with 2n−6 edges and TAR above 60°, so any stronger bound would need additional hypotheses.","Deciding whether a graph can be drawn with total angular resolution at least 60° is NP-hard, so no polynomial-time recognition algorithm exists unless P=NP.","The same techniques yield related bounds for larger angles: TAR≥90° forces m≤2n−2√n, and TAR>120° forces m≤n for n≥7.","The paper conjectures a parameterized generalization for angles of the form (k−2)/k·90°, bounding the edge count by 2n−2−⌊k/2⌋ up to constant-size exceptions."],"supporting_citations":[{"why":"Supplies the NP-hardness reduction template from angular resolution 90° that the paper adapts to total angular resolution at 60°.","marker":"[7]"},{"why":"Gives the general upper bound 180°/α (3n−6) for α-angle crossing drawings that the 2n−6 bound improves at α>60°.","marker":"[6]"},{"why":"Provides the previous best bound of 6.5n−20 for crossing resolution above 60°, which the new bound strengthens.","marker":"[1]"},{"why":"Establishes the 4n−10 edge bound for RAC drawings, the 90° special case that motivates the angular threshold question.","marker":"[5]"},{"why":"Introduces the total resolution measure and supplies drawings of complete graphs with high total angular resolution.","marker":"[3]"},{"why":"Proves NP-hardness of the straight-line RAC drawing problem, a related hardness result for right-angle crossings.","marker":"[2]"}],"fun_headline_variants":["Tight edge bound at 60° total angular resolution","At 60°, graphs can't have more than 2n−6 edges","NP-hard to decide if a graph has 60° resolution","60° total angular resolution: edge cap is sharp","Graphs with >60° angles obey 2n−6 edge limit"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The NP-hardness proof relies on the unproved assertion that every 60°-resolution embedding of the clause, variable, and connector gadgets is unique up to rotation, scaling, and reflection, and that the enclosing triangular frame cannot flex; if a gadget admitted a different 60° embedding, the binary orientation of variables would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Tight edge bound at 60° total angular resolution","At 60°, graphs can't have more than 2n−6 edges","NP-hard to decide if a graph has 60° resolution","60° total angular resolution: edge cap is sharp","Graphs with >60° angles obey 2n−6 edge limit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000299,"raw_usage":{"total_tokens":1684,"prompt_tokens":853,"completion_tokens":831,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":469,"completion_tokens_details":{"reasoning_tokens":741}},"tokens_in":469,"tokens_out":831,"duration_ms":7518,"temperature":1.0,"reasoning_tokens":741,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:43:20.759578+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for a continuous family of drawings of the connector gadget (two triangles sharing an edge) in which all angles stay at least 60° but the distance between the two outer vertices changes; finding such a flex would invalidate the rigidity claim and break the NP-hardness reduction. For the edge bound, exhibit any graph outside the listed exceptions with TAR(G)>60° and more than 2n−6 edges; even one example would refute Theorem 1.","supporting_citations":[{"cited_title":"o rster, H., G eckeler, C., H oll \\","cited_arxiv_id":null,"evidence_quote":"Gives the general upper bound 180°/α (3n−6) for α-angle crossing drawings that the 2n−6 bound improves at α>60°."},{"cited_title":"T he C omputer J ournal 56(7), 887--900 (2013)","cited_arxiv_id":null,"evidence_quote":"Establishes the 4n−10 edge bound for RAC drawings, the 90° special case that motivates the angular threshold question."}],"review_version":1}