Angular resolution (graph drawing)

In graph drawing, the angular resolution of a drawing of a graph refers to the sharpest angle formed by any two edges that meet at a common vertex of the drawing.

Formann et al. (1993) observed that every straight-line drawing of a graph with maximum degree $d$ has angular resolution at most $2π/ d$ : if $v$ is a vertex of degree $d$ , then the edges incident to $v$ partition the space around $v$ into $d$ wedges with total angle $2π$ , and the smallest of these wedges must have an angle of at most $2π/ d$ . More strongly, if a graph is $d$ -regular, it must have angular resolution less than ${\frac {\pi }{d-1}}$ , because this is the best resolution that can be achieved for a vertex on the convex hull of the drawing.

As Formann et al. (1993) showed, the largest possible angular resolution of a graph $G$ is closely related to the chromatic number of the square $G 2$ , the graph on the same vertex set in which pairs of vertices are connected by an edge whenever their distance in $G$ is at most two. If $G 2$ can be colored with $χ$ colors, then G may be drawn with angular resolution $π/χ - ε$ , for any $ε > 0$ , by assigning distinct colors to the vertices of a regular χ-gon and placing each vertex of $G$ close to the polygon vertex with the same color. Using this construction, they showed that every graph with maximum degree $d$ has a drawing with angular resolution proportional to $1/ d 2$ . This bound is close to tight: they used the probabilistic method to prove the existence of graphs with maximum degree $d$ whose drawings all have angular resolution $O\left({\frac {\log d}{d^{2}}}\right)$ .

...
Wikipedia