View source for Angular resolution (graph drawing)

{{Short description|Sharpest angle between edges at a vertex}}
[[File:Hypercubestar.svg|thumb|upright=1.1|This drawing of a [[Hypercube graph|hypercube graph]] has angular resolution {{math|π/4}}.]]
In [[Graph drawing|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|Formann|Hagerup|Haralambides|Kaufmann|1993}} observed that every straight-line drawing of a graph with maximum degree {{mvar|d}} has angular resolution at most  {{math|2π/''d''}}: if {{mvar|v}} is a vertex of degree {{mvar|d}}, then the edges incident to {{mvar|v}} partition the space around {{mvar|v}} into {{mvar|d}} wedges with total angle {{math|2π}}, and the smallest of these wedges must have an angle of at most {{math|2π/''d''}}. More strongly, if a graph is {{mvar|d}}-[[Regular graph|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|convex hull]] of the drawing.

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

===Existence of optimal drawings===
{{harvtxt|Formann|Hagerup|Haralambides|Kaufmann|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. Specifically, they exhibited an 11-vertex graph that has drawings of angular resolution  {{math|π/3 − ε}} for any  {{math|ε > 0}}, but that does not have a drawing of angular resolution exactly  {{math|π/3}}.

==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 (graph drawing)|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.<ref>{{harvtxt|Duncan|Eppstein|Goodrich|Kobourov|2011}}; {{harvtxt|Halupczok|Schulz|2011}}.</ref>

===Outerplanar graphs===
Perfect angular resolution is not always possible for [[Outerplanar graph|outerplanar graph]]s, 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|d}} has an outerplanar drawing with angular resolution proportional to {{math|1/''d''}}.<ref>{{harvtxt|Malitz|Papakostas|1994}}; {{harvtxt|Garg|Tamassia|1994}}.</ref>

===Planar graphs===
For [[Planar graph|planar graph]]s with maximum degree {{mvar|d}}, the square-coloring technique of {{harvtxt|Formann|Hagerup|Haralambides|Kaufmann|1993}} provides a drawing with angular resolution proportional to {{math|1/''d''}}, because the square of a planar graph must have chromatic number proportional to {{mvar|d}}. 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>.<ref>{{harvtxt|Kramer|Kramer|2008}}; {{harvtxt|Molloy|Salavatipour|2005}}.</ref> 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|O(1/''d''<sup>3</sup>)}}, where {{mvar|d}} is the degree of the graph.<ref>{{harvtxt|Garg|Tamassia|1994}}.</ref> 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|Malitz|Papakostas|1994}} used the [[Circle packing theorem|circle packing theorem]] and [[Ring lemma|ring lemma]] to show that every [[Planar graph|planar graph]] with maximum degree {{mvar|d}} has a planar drawing whose angular resolution is at worst an exponential function of {{mvar|d}}, 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|d}} has a drawing with angular resolution {{math|2π/''d''}}, even in the special case that  {{math|1=''d'' = 4}}.<ref>{{harvtxt|Formann|Hagerup|Haralambides|Kaufmann|1993}}; {{harvtxt|Garg|Tamassia|1995}}.</ref> 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.<ref>{{harvtxt|Carlson|Eppstein|2007}}; {{harvtxt|Eppstein|Wortman|2011}}.</ref>

==History==
Angular resolution was first defined by {{harvtxt|Formann|Hagerup|Haralambides|Kaufmann|1993}}.

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,<ref>{{harvtxt|Kant|1996}}; {{harvtxt|Gutwenger|Mutzel|1998}}.</ref> circular arcs,<ref>{{harvtxt|Cheng|Duncan|Goodrich|Kobourov|1999}}; {{harvtxt|Duncan|Eppstein|Goodrich|Kobourov|2011}}.</ref> or spline curves.<ref>{{harvtxt|Brandes|Shubina|Tamassia|2000}}; {{harvtxt|Finkel|Tamassia|2005}}.</ref>

The angular resolution of a graph is closely related to its crossing resolution, the angle formed by [[Crossing number (graph theory)|crossings]] in a drawing of the graph. In particular, [[RAC drawing]] seeks to ensure that these angles are all [[Right angle|right angle]]s, the largest crossing angle possible.{{sfnp|Didimo|Eades|Liotta|2009}}

==Notes==
{{reflist|colwidth=30em}}

==References==
{{refbegin|colwidth=30em}}
*{{citation
 | last2 = Shubina | first2 = Galina
 | contribution = Improving angular resolution in visualizations of geographic networks
 | title = Data Visualization 2000: Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization in Amsterdam, the Netherlands, May 29-31, 2000
 | url = http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-77811
 | year = 2000| doi = 10.1007/978-3-7091-6783-0_3 | isbn = 9783211835159 }}.
*{{citation
 | last1 = Carlson | first1 = Josiah
 | editor1-last = Kaufmann | editor1-first = Michael
 | arxiv = cs.CG/0607113
 | contribution = Trees with convex faces and optimal angles
 | doi = 10.1007/978-3-540-70904-6_9
 | pages = 77–88
 | publisher = Springer-Verlag
 | series = LNCS
 | title = Proc. 14th Int. Symp. Graph Drawing (GD'06)
 | volume = 4372
 | year = 2007| s2cid = 12598338
 }}.
*{{citation
 | last1 = Cheng | first1 = C. C.
 | last2 = Duncan | first2 = C. A.
 | last4 = Kobourov | first4 = S. G.
 | contribution = Drawing planar graphs with circular arcs
 | doi = 10.1007/3-540-46648-7_12
 | pages = 117–126
 | publisher = Springer-Verlag
 | series = [[Lecture Notes in Computer Science]]
 | title = Graph Drawing, 7th International Symposium, GD'99, Štirín Castle, Czech Republic September 15–19, 1999, Proceedings
 | volume = 1731
 | year = 1999| doi-access = free
 }}.
*{{citation
 | last1 = Didimo | first1 = Walter
 | last3 = Liotta | first3 = Giuseppe
 | contribution = Drawing graphs with right angle crossings
 | doi = 10.1007/978-3-642-03367-4_19
 | pages = 206–217
 | series = Lecture Notes in Computer Science
 | title = Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings
 | volume = 5664
 | year = 2009}}.
*{{citation
 | last1 = Duncan | first1 = Christian A.
 | last4 = Kobourov | first4 = Stephen G.
 | last5 = Nöllenburg | first5 = Martin
 | editor1-last = Brandes | editor1-first = Ulrik
 | editor2-last = Cornelsen | editor2-first = Sabine
 | arxiv = 1009.0581
 | contribution = Drawing trees with perfect angular resolution and polynomial area
 | doi = 10.1007/978-3-642-18469-7_17
 | pages = 183–194
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proc. 18th Int. Symp. Graph Drawing
 | volume = 6502
 | year = 2011}}.
*{{citation
 | last2 = Wortman | first2 = K.
 | arxiv = 0907.5474
 | issue = 4
 | journal = [[Journal of Graph Algorithms and Applications]]
 | pages = 551–564
 | title = Optimal angular resolution for face-symmetric drawings
 | volume = 15
 | year = 2011 | doi=10.7155/jgaa.00238| s2cid = 10356432 }}.
*{{citation
 | last1 = Finkel | first1 = Benjamin
 | contribution = Curvilinear graph drawing using the force-directed method
 | doi = 10.1007/978-3-540-31843-9_46
 | pages = 448–453
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers
 | volume = 3383
 | year = 2005| doi-access = free
 }}.
*{{citation
 | last1 = Formann | first1 = M.
 | last2 = Hagerup | first2 = T.
 | last3 = Haralambides | first3 = J.
 | last4 = Kaufmann | first4 = M.
 | last6 = Symvonis | first6 = A.
 | doi = 10.1137/0222063
 | issue = 5
 | journal = [[SIAM Journal on Computing]]
 | mr = 1237161
 | pages = 1035–1052
 | title = Drawing graphs in the plane with high resolution
 | volume = 22
 | year = 1993}}.
*{{citation
 | last1 = Garg | first1 = Ashim
 | contribution = Planar drawings and angular resolution: Algorithms and bounds
 | doi = 10.1007/BFb0049393
 | pages = 12–23
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Algorithms, Second Annual European Symposium, Utrecht, The Netherlands, September 26–28, 1994, Proceedings
 | volume = 855
 | year = 1994}}.
*{{citation
 | last1 = Garg | first1 = Ashim
 | last2 = Tamassia | first2 = Roberto
 | editor1-last = Tamassia | editor1-first = Roberto
 | editor2-last = Tollis | editor2-first = Ioannis
 | contribution = On the computational complexity of upward and rectilinear planarity testing
 | doi = 10.1007/3-540-58950-3_384
 | pages = 286–297
 | publisher = Springer Berlin / Heidelberg
 | series = Lecture Notes in Computer Science
 | title = Graph Drawing
 | volume = 894
 | year = 1995| doi-access = free
 }}.
*{{citation
 | last1 = Gutwenger | first1 = Carsten
 | contribution = Planar polyline drawings with good angular resolution
 | doi = 10.1007/3-540-37623-2_13
 | location = Berlin
 | mr = 1717450
 | pages = 167–182
 | publisher = Springer
 | series = Lecture Notes in Comput. Sci.
 | title = Graph drawing (Montréal, QC, 1998)
 | volume = 1547
 | year = 1998}}.
*{{citation
 | last1 = Halupczok | first1 = Immanuel
 | last2 = Schulz | first2 = André
 | contribution = Pinning balloons with perfect angles and optimal area
 | title = [[International Symposium on Graph Drawing|Proceedings of the 19th International Symposium on Graph Drawing]]
 | year = 2011}}.
*{{citation
 | last = Kant | first = G.
 | doi = 10.1007/s004539900035
 | issue = 1
 | journal = Algorithmica
 | mr = 1394492
 | pages = 4–32
 | title = Drawing planar graphs using the canonical ordering
 | volume = 16
 | year = 1996| hdl = 1874/16676
 | hdl-access = free
 }}.
*{{citation
 | last1 = Kramer | first1 = Florica
 | last2 = Kramer | first2 = Horst
 | doi = 10.1016/j.disc.2006.11.059
 | issue = 2–3
 | journal = Discrete Mathematics
 | mr = 2378044
 | pages = 422–426
 | title = A survey on the distance-colouring of graphs
 | volume = 308
 | year = 2008| doi-access = 
 }}.
*{{citation
 | last1 = Malitz | first1 = Seth
 | last2 = Papakostas | first2 = Achilleas
 | doi = 10.1137/S0895480193242931
 | issue = 2
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 1271989
 | pages = 172–183
 | title = On the angular resolution of planar graphs
 | volume = 7
 | year = 1994}}.
*{{citation
 | last1 = Molloy | first1 = Michael
 | last2 = Salavatipour | first2 = Mohammad R.
 | doi = 10.1016/j.jctb.2004.12.005
 | issue = 2
 | journal = Journal of Combinatorial Theory | series = Series B
 | mr = 2145512
 | pages = 189–213
 | title = A bound on the chromatic number of the square of a planar graph
 | volume = 94
 | year = 2005| hdl = 1807/9473
 | hdl-access = free
 }}.
{{refend}}

[[Category:Graph drawing]]

{{Sourceattribution|Angular resolution (graph drawing)}}