2019/08/18 by Oswin Aichholzer, Aichholzer, Oswin, Matias Korman +11
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1908.06504
openalex publication_date 2019/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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∘ 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∘ is NP-hard.