Английская Википедия:Angular resolution (graph drawing)
In graph drawing, the angular resolution of a drawing of a graph is the sharpest angle formed by any two edges that meet at a common vertex of the drawing.
Properties
Relation to vertex degree
Шаблон:Harvtxt observed that every straight-line drawing of a graph with maximum degree Шаблон:Mvar has angular resolution at most Шаблон:Math: if Шаблон:Mvar is a vertex of degree Шаблон:Mvar, then the edges incident to Шаблон:Mvar partition the space around Шаблон:Mvar into Шаблон:Mvar wedges with total angle Шаблон:Math, and the smallest of these wedges must have an angle of at most Шаблон:Math. More strongly, if a graph is Шаблон:Mvar-regular, it must have angular resolution less than <math>\frac{\pi}{d-1}</math>, because this is the best resolution that can be achieved for a vertex on the convex hull of the drawing.
Relation to graph coloring
As Шаблон:Harvtxt showed, the largest possible angular resolution of a graph Шаблон:Mvar is closely related to the chromatic number of the square Шаблон:Math, the graph on the same vertex set in which pairs of vertices are connected by an edge whenever their distance in Шаблон:Mvar is at most two. If Шаблон:Math can be colored with Шаблон:Math colors, then G may be drawn with angular resolution Шаблон:Math, for any Шаблон:Math, by assigning distinct colors to the vertices of a [[regular polygon|regular Шаблон:Math-gon]] and placing each vertex of Шаблон:Mvar close to the polygon vertex with the same color. Using this construction, they showed that every graph with maximum degree Шаблон:Mvar has a drawing with angular resolution proportional to Шаблон:Math. This bound is close to tight: they used the probabilistic method to prove the existence of graphs with maximum degree Шаблон:Mvar whose drawings all have angular resolution <math>O\left(\frac{\log d}{d^2}\right)</math>.
Existence of optimal drawings
Шаблон:Harvtxt 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. Specifically, they exhibited an 11-vertex graph that has drawings of angular resolution Шаблон:Math for any Шаблон:Math, but that does not have a drawing of angular resolution exactly Шаблон:Math.
Special classes of graphs
Trees
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 already determined as part of the input to the problem, then achieving perfect angular resolution with no crossings may sometimes require exponential area.[1]
Outerplanar graphs
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. Nonetheless, every outerplanar graph of maximum degree Шаблон:Mvar has an outerplanar drawing with angular resolution proportional to Шаблон:Math.[2]
Planar graphs
For planar graphs with maximum degree Шаблон:Mvar, the square-coloring technique of Шаблон:Harvtxt provides a drawing with angular resolution proportional to Шаблон:Math, because the square of a planar graph must have chromatic number proportional to Шаблон:Mvar. More precisely, Wegner conjectured in 1977 that the chromatic number of the square of a planar graph is at most <math>\max\left(d+5, \frac{3d}{2}+1\right)</math>, and it is known that the chromatic number is at most <math>\frac{5d}{3}+O(1)</math>.[3] However, the drawings resulting from this technique are generally not planar.
For some planar graphs, the optimal angular resolution of a planar straight-line drawing is Шаблон:Math, where Шаблон:Mvar is the degree of the graph.[4] Additionally, such a drawing may be forced to use very long edges, longer by an exponential factor than the shortest edges in the drawing. Шаблон:Harvtxt used the circle packing theorem and ring lemma to show that every planar graph with maximum degree Шаблон:Mvar has a planar drawing whose angular resolution is at worst an exponential function of Шаблон:Mvar, independent of the number of vertices in the graph.
Computational complexity
It is NP-hard to determine whether a given graph of maximum degree Шаблон:Mvar has a drawing with angular resolution Шаблон:Math, even in the special case that Шаблон:Math.[5] However, for certain restricted classes of drawings, including drawings of trees in which extending the leaves to infinity produces a convex subdivision of the plane as well as drawings of planar graphs in which each bounded face is a centrally-symmetric polygon, a drawing of optimal angular resolution may be found in polynomial time.[6]
History
Angular resolution was first defined by Шаблон:Harvtxt.
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,[7] circular arcs,[8] or spline curves.[9]
The angular resolution of a graph is closely related to its crossing resolution, the angle formed by crossings in a drawing of the graph. In particular, RAC drawing seeks to ensure that these angles are all right angles, the largest crossing angle possible.Шаблон:Sfnp
Notes
References
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
