
The authors consider drawings of graphs in the plane such that edges are straight line segments and the minimum angle formed by any pair of incident edges is as large as possible; this maximum is called a resolution of a graph. For any graph with maximum valency \(d\) the resolution \(R\) of the graph satisfies the inequality \(\Omega(d^{-2})\leq R\leq 2\pi/d\). Examples of various classes of graphs are exhibited for which \(R=\Theta(1/d)\), or \(R=O(d^{-2}\log d)\). It is also shown that the problem of deciding if \(R=2\pi/d\) for a graph is NP-hard for \(d=4\).
straight line segments, Analysis of algorithms and problem complexity, resolution, NP-hard, Planar graphs; geometric and topological aspects of graph theory, drawings, Graph theory, Coloring of graphs and hypergraphs, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), plane
straight line segments, Analysis of algorithms and problem complexity, resolution, NP-hard, Planar graphs; geometric and topological aspects of graph theory, drawings, Graph theory, Coloring of graphs and hypergraphs, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), plane
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 63 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
