Graphs with large total angular resolution
Preprint
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.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- A Heuristic Approach Towards Drawings of Graphs With High Crossing ResolutionThe Computer Journal, 2019
- Improving multiple aesthetics produces better graph drawingsJournal of Visual Languages & Computing, 2013
- Drawing Trees with Perfect Angular Resolution and Polynomial AreaDiscrete & Computational Geometry, 2012
- Maximizing the Total Resolution of GraphsThe Computer Journal, 2012
- Drawing graphs with right angle crossingsTheoretical Computer Science, 2011
- On the maximum number of edges in quasi-planar graphsJournal of Combinatorial Theory, Series A, 2007
- Polar Coordinate Drawing of Planar Graphs with Good Angular ResolutionJournal of Graph Algorithms and Applications, 2003
- On the Angular Resolution of Planar GraphsSIAM Journal on Discrete Mathematics, 1994
- Drawing Graphs in the Plane with High ResolutionSIAM Journal on Computing, 1993
- Self-dual configurations and regular graphsBulletin of the American Mathematical Society, 1950