Pith. sign in

REVIEW 3 major objections 4 minor 13 references

Graphs with large total angular resolution

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict The 2n−6 extremal bound is solid and checkable; the NP-hardness proof rests on an unproved—quite possibly false—rigidity claim. read the letter →

arxiv 1908.06504 v2 pith:LAUSTFRQ submitted 2019-08-18 cs.CG

Oswin Aichholzer , Matias Korman , Yoshio Okamoto , Irene Parada , Daniel Perz , André van Renssen , Birgit Vogtenhuber This is my paper · ORCID
classification cs.CG MSC 05C1005C6268Q1768R10
keywords totalangularresolutioncrossinggraphdrawingNP-hardnessextremaltheoryplanar60-degreethreshold
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 3 / Appendix E] 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.
  2. [Section 4, Conclusion] 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.
  3. [Appendix C, Lemma 4] 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.
minor comments (4)
  1. [Section 3] 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.
  2. [Theorem 1 proof] The sentence 'Applying Lemma 1 to every component gives m ≤ 2m − 6' should read m ≤ 2n − 6; as typeset the inequality is nonsensical.
  3. [Section 2] 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.
  4. [Appendix D, Lemma 5] The computation 'm = 2 · 4 − 6 = 2' is confusingly written; the conclusion is correct, but the sentence should be clarified.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the edge bounds follow from Euler's formula and elementary angle-counting, and the NP-hardness reduction does not fit or import its conclusion.

full rationale

The paper's main upper bound (Theorem 1) is derived from Lemma 1, which uses Euler's formula on the planarized drawing and the fact that every bounded cell has size at least four when TAR(D) > 60 degrees. Lemma 2 and Lemma 3 iterate this cell-counting argument with Observation 1 (sum of interior angles), and Theorem 1 combines the plane-drawing lemma with a planarization argument. No fitted parameter is introduced, no quantity is predicted from a subset of the same data, and the proof does not rely on any author-defined uniqueness theorem or load-bearing self-citation: the cited results are external (Euler's formula, Formann et al. for the 90-degree NP-hardness base). The NP-hardness proof (Theorem 2, Appendix E) does assert that the frame and each gadget have a unique total-angular-resolution-60 embedding up to rotation, scaling, and reflection, and this rigidity claim is not proved in the text. That is a genuine correctness gap: if a flexed embedding existed, the binary variable orientation and the contradiction based on lines l1 and l2 could fail. However, this is an unproved premise of the reduction, not a conclusion that has been built into its definition; the satisfiability direction is not equivalent to the uniqueness assertion by construction. Hence no circular step meets the evidentiary standard of the review, and the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted constants and no invented physical entities. It relies on standard planar graph arguments and elementary angle geometry. The one non-standard load-bearing premise is the asserted uniqueness of 60° gadget embeddings in the NP-hardness proof.

assumptions (4)
  • standard math Euler's formula for the planarized drawing P(D).
    Used in Lemma 1 to relate n, m, crossing count, and number of faces.
  • standard math The interior angle sum of a simple polygon with p vertices is 180(p − 2) degrees.
    Used in Observation 1 to bound the number of interior edges incident to the outer polygon.
  • domain assumption The drawing model is straight-line, with angles measured both at shared vertices and at crossings.
    This is stated in Section 1 and is the defining setting for total angular resolution.
  • ad hoc to paper Every embedding of the clause, variable, and connector gadgets with TAR = 60° is unique up to rotation, scaling, and reflection.
    Asserted in Section 3 and Appendix E without proof; it is load-bearing for the rigidity of the frame and the binary orientation of the variable gadgets in the NP-hardness reduction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graphs with large total angular resolution." pith.science (2026). https://pith.science/paper/LAUSTFRQ

@misc{pith2026190806504,
  author       = {Pith},
  title        = {Pith review of: Graphs with large total angular resolution},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LAUSTFRQ}},
  note         = {Machine review of arXiv:1908.06504}
}
abstract

The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove that, up to a finite number of well specified exceptions of constant size, the number of edges of a graph with $n$ vertices and a total angular resolution greater than $60^{\circ}$ is bounded by $2n-6$. This bound is tight. In addition, we show that deciding whether a graph has total angular resolution at least $60^{\circ}$ is NP-hard.

Figures

Figures reproduced from arXiv: 1908.06504 by the authors.

Figure 1
Figure 1. (a) The drawings of exception E9. (b) A drawing [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Gadgets and frame of the NP-hardness proof. For connecting the gadgets, we build a 3-sided frame; see [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Connections between clause and literal vertices in the [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Two separated vertices inside a 6-gon. B All exceptions This appendix contains drawings depicting all exceptions of Lemma 3 and The￾orem 1 ( [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: All exceptions for Lemma 3 and Theorem 1 [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Replacing vertex of degree 4 of the drawing in Fig. 1(a) (left) with a [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 7 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sentence := #2 'after.sentence := #3 '...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize ":" * " " *...

  3. [3]

    Journal of Combinatorial Theory, Series A 114, 563--571 (2007)

    A ckerman, E., T ardos, G.: On the maximum number of edges in quasi-planar graphs. Journal of Combinatorial Theory, Series A 114, 563--571 (2007). doi:10.1016/j.jcta.2006.08.002

    doi:10.1016/j.jcta.2006.08.002 2007

  4. [4]

    In: 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011)

    A rgyriou, E.N., B ekos, M.A., S ymvonis, A.: The S traight- L ine RAC D rawing P roblem is NP - H ard. In: 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011). pp. 74--85. Springer, Berlin, Heidelberg (2011). doi:10.1007/978-3-642-18381-2\_6

    doi:10.1007/978-3-642-18381-2 2011

  5. [5]

    T he C omputer J ournal 56(7), 887--900 (2013)

    A rgyriou, E.N., B ekos, M.A., S ymvonis, A.: M aximizing the T otal R esolution of G raphs. T he C omputer J ournal 56(7), 887--900 (2013). doi:10.1093/comjnl/bxs088

    work page doi:10.1093/comjnl/bxs088 2013

  6. [6]

    o rster, H., G eckeler, C., H oll \

    B ekos, M.A., F \"o rster, H., G eckeler, C., H oll \"a nder, L., K aufmann, M., S pallek, A.M., S plett, J.: A H euristic A pproach T owards D rawings of G raphs with H igh C rossing R esolution. In: Biedl, T., Kerren, A. (eds.) 26th International Symposium on Graph D rawing and Network Visualization (GD 2018). pp. 271--285. Springer, Cham (2018). doi:10...

    work page doi:10.1007/978--3--030--04414--5 2018

  7. [7]

    Theoretical C omputer S cience 412(39), 5156--5166 (2011)

    D idimo, W., E ades, P., L iotta, G.: Drawing graphs with right angle crossings. Theoretical C omputer S cience 412(39), 5156--5166 (2011). doi:10.1016/j.tcs.2011.05.025

    doi:10.1016/j.tcs.2011.05.025 2011

  8. [8]

    Chicago Journal of Theoretical Computer Science 4, 1--14 (2011)

    D ujmovic, V., G udmundsson, J., M orin, P., W olle, T.: Notes on large angle crossing graphs. Chicago Journal of Theoretical Computer Science 4, 1--14 (2011). doi:10.4086/cjtcs.2011.004

    work page doi:10.4086/cjtcs.2011.004 2011

Show all 13 references
  1. [9]

    SIAM J ournal on C omputing 22, 1035--1052 (1993)

    F ormann, M., H agerup, T., H aralambides, J., K aufmann, M., L eighton, F.T., S ymvonis, A., W elzl, E., W oeginger, G.J.: D rawing G raphs in the P lane with H igh R esolution. SIAM J ournal on C omputing 22, 1035--1052 (1993). doi:10.1137/0222063

    1993 doi

  2. [10]

    In: 2007 6th International Asia-Pacific Symposium on Visualization

    Huang, W.: Using eye tracking to investigate graph layout effects. In: 2007 6th International Asia-Pacific Symposium on Visualization. pp. 97--100. IEEE (2007). doi:10.1109/APVIS.2007.329282

    2007

  3. [11]

    Journal of V isual L anguages & C omputing 24(4), 262--272 (2013)

    H uang, W., E ades, P., H ong, S.H., L in, C.: Improving multiple aesthetics produces better graph drawings. Journal of V isual L anguages & C omputing 24(4), 262--272 (2013). doi:10.1016/j.jvlc.2011.12.002

    2013 doi

  4. [12]

    In: 2008 IEEE Pacific Visualization Symposium

    H uang, W., H ong, S.H., E ades, P.: Effects of C rossing A ngles. In: 2008 IEEE Pacific Visualization Symposium. pp. 41--46 (2008). doi:10.1109/PACIFICVIS.2008.4475457

    2008

  5. [13]

    In: Brandes, U., Cornelsen, S

    van K reveld, M.: The quality ratio of RAC drawings and planar drawings of planar graphs. In: Brandes, U., Cornelsen, S. (eds.) 18th I nternational S ymposium on G raph D rawing (GD 2010). pp. 371--376. Springer, Berlin, Heidelberg (2010). doi:10.1007/978--3--642--18469-7\_34

    2010 doi

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.