In graph drawing

Graph drawing

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...

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

Angular resolution was first defined by . They observed that every drawing of a graph with maximum degree d has angular resolution at most , and they proved that it is NP-hard to determine whether a given graph has a drawing meeting this bound, even in the special case that . They also gave an example showing that not every graph has a drawing achieving the maximum possible angle resolution for that graph: specifically, they exhibited an 11-vertex graph that has drawings of angular resolution for any , but that does not have a drawing of angular resolution exactly .

As showed, the largest possible angular resolution of a graph is closely related to the chromatic number of the square , the graph on the same vertex set in which pairs of vertices are connected by an edge whenever their distance in is at most two. If can be colored with colors, then G may be drawn with angular resolution , for any , by assigning distinct colors to the vertices of a regular χ-gon

Regular polygon

A regular polygon is a polygon that is equiangular and equilateral . Regular polygons may be convex or star.-General properties:...

 and placing each vertex of close to the polygon vertex with the same color. Using this construction, they showed that every graph with maximum degree has a drawing with angular resolution proportional to . This bound is close to tight: they used the probabilistic method

Probabilistic method

The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the...

 to prove the existence of graphs with maximum degree whose drawings all have angular resolution .

For planar graph

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

s with maximum degree , the square-coloring technique of provides a drawing with angular resolution proportional to , because the square of a planar graph must have chromatic number proportional to . However, the drawings resulting from this technique are not planar.
used the circle packing theorem

Circle packing theorem

The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint...

 to show that every planar graph

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

 with maximum degree has a planar drawing whose angular resolution is an exponential function of , independent of the number of vertices in the graph. Such a drawing may be forced to use very long edges, longer by an exponential factor than the shortest edges in the drawing. For some planar graphs, it may be necessary to use angular resolution that is at least cubic in . However, outerplanar graph

Outerplanar graph

In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...

s have outerplanar drawings with much better angular resolution, proportional to .

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. Moreover, if the edges may be freely permuted around each vertex, then such a drawing is possible, without crossings, with all edges unit length or higher, and with the entire drawing fitting within a bounding box of polynomial area. However, if the cyclic ordering of the edges around each vertex is fixed, then achieving perfect angular resolution with no crossings requires exponential area.

Although originally defined only for straight-line drawings of graphs, later authors have also investigated the angular resolution of drawings in which the edges are polygonal chains, circular arcs, or spline curves.