Angular resolution (graph 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.

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 G2, 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.

Using this construction, they showed that every graph with maximum degree d has a drawing with angular resolution proportional to 1/d2.

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

Formann et al. (1993) provided an example showing that there exist graphs that do not have a drawing achieving the maximum possible angular resolution; instead, these graphs have a family of drawings whose angular resolutions tend towards some limiting value without reaching it.

Every tree may be drawn in such a way that the edges are equally spaced around each vertex, a property known as perfect angular resolution.

However, if the cyclic ordering of the edges around each vertex is already determined as part of the input to the problem, then achieving perfect angular resolution with no crossings may sometimes require exponential area.

[1] Perfect angular resolution is not always possible for outerplanar graphs, because vertices on the convex hull of the drawing with degree greater than one cannot have their incident edges equally spaced around them.

Malitz & Papakostas (1994) used the circle packing theorem and ring lemma to show that every planar graph with maximum degree d has a planar drawing whose angular resolution is at worst an exponential function of d, independent of the number of vertices in the graph.

It is NP-hard to determine whether a given graph of maximum degree d has a drawing with angular resolution 2π/d, even in the special case that d = 4.