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.
Angular resolution was first defined by Formann et al. (1993). They observed that every drawing of a graph with maximum degree d has angular resolution at most 2π/d, and they proved that it is NP-hard to determine whether a given graph has a drawing meeting this lower bound, even in the special case that d = 4. 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 π/3 − ε for any ε > 0, but that does not have a drawing of angular resolution exactly π/3.
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. If G2 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/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 O(log d/d2).
For planar graphs with maximum degree d, the square-coloring technique of Formann et al. (1993) provides a drawing with angular resolution proportional to 1/d, because the square of a planar graph must have degree proportional to that of the graph itself. However, the drawings resulting from this technique are not planar. Malitz & Papakostas (1994) used the circle packing theorem to show that every planar graph with maximum degree d has a planar drawing whose angular resolution is an exponential function of d, 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 d.[1] However, outerplanar graphs have outerplanar drawings with much better angular resolution, proportional to 1/d.[2]
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.[3]
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,[4] circular arcs,[5] or spline curves.[6]
Notes
References
- Brandes, Ulrik; Shubina, Galina; Tamassia, Roberto (2000), "Improving angular resolution in visualizations of geographic networks", Data Visualization 2000: Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization in Amsterdam, The Netherlands, May 29-31, 2000.
- Cheng, C. C.; Duncan, C. A.; Goodrich, M. T.; Kobourov, S. G. (1999), "Drawing planar graphs with circular arcs", Graph Drawing, 7th International Symposium, GD'99, Štirín Castle, Czech Republic September 15–19, 1999, Proceedings, Lecture Notes in Computer Science, vol. 1731, Springer-Verlag, pp. 117–126, doi:10.1007/3-540-46648-7_12.
- Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Nöllenburg, Martin (2011), "Drawing trees with perfect angular resolution and polynomial area", in Brandes, Ulrik; Cornelsen, Sabine (eds.), Proc. 18th Int. Symp. Graph Drawing, Lecture Notes in Computer Science, vol. 6502, Springer-Verlag, pp. 183–194, arXiv:1009.0581, doi:10.1007/978-3-642-18469-7_17.
- Finkel, Benjamin; Tamassia, Roberto (2005), "Curvilinear graph drawing using the force-directed method", Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers, Lecture Notes in Computer Science, vol. 3383, Springer-Verlag, pp. 448–453, doi:10.1007/978-3-540-31843-9_46.
- Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, F. T.; Symvonis, A.; Welzl, E.; Woeginger, G. (1993), "Drawing graphs in the plane with high resolution", SIAM Journal on Computing, 22 (5): 1035–1052, doi:10.1137/0222063, MR 1237161.
- Garg, Ashim; Tamassia, Roberto (1994), "Planar drawings and angular resolution: Algorithms and bounds", Algorithms, Second Annual European Symposium, Utrecht, The Netherlands, September 26–28, 1994, Proceedings, Lecture Notes in Computer Science, vol. 855, Springer-Verlag, pp. 12–23, doi:10.1007/BFb0049393.
- Gutwenger, Carsten; Mutzel, Petra (1998), "Planar polyline drawings with good angular resolution", Graph drawing (Montréal, QC, 1998), Lecture Notes in Comput. Sci., vol. 1547, Berlin: Springer, pp. 167–182, doi:10.1007/3-540-37623-2_13, MR 1717450.
- Halupczok, Immanuel; Schulz, André (2011), "Pinning balloons with perfect angles and optimal area", Proceedings of the 19th International Symposium on Graph Drawing.
- Kant, G. (1996), "Drawing planar graphs using the canonical ordering", Algorithmica, 16 (1): 4–32, doi:10.1007/s004539900035, MR 1394492.
- Malitz, Seth; Papakostas, Achilleas (1994), "On the angular resolution of planar graphs", SIAM Journal on Discrete Mathematics, 7 (2): 172–183, doi:10.1137/S0895480193242931, MR 1271989.