In graph drawing, the area used by a drawing is a commonly used way of measuring its quality.
Definition
editFor a drawing style in which the vertices are placed on the integer lattice, the area of the drawing may be defined as the area of the smallest axis-aligned bounding box of the drawing: that is, it the product of the largest difference in x-coordinates of two vertices with the largest difference in y-coordinates. For other drawing styles, in which vertices are placed more freely, the drawing may be scaled so that the closest pair of vertices have distance one from each other, after which the area can again be defined as the area of a smallest bounding box of a drawing. Alternatively, the area can be defined as the area of the convex hull of the drawing, again after appropriate scaling.[1]
Polynomial bounds
editFor straight-line drawings of planar graphs with n vertices, the optimal worst-case bound on the area of a drawing is Θ(n2). The nested triangles graph requires this much area no matter how it is embedded,[2] and several methods are known that can draw planar graphs with at most quadratic area.[3][4] Binary trees, and trees of bounded degree more generally, have drawings with linear or near-linear area, depending on the drawing style.[5][6][7][8][9] Every outerplanar graph has a straight-line outerplanar drawing with area subquadratic in its number of vertices,[10][11] If bends or crossings are allowed, then outerplanar graphs have drawings with near-linear area.[12][13] However, drawing series–parallel graphs requires an area larger than n multiplied by a superpolylogarithmic factor, even if edges can be drawn as polylines.[14]
Exponential bounds
editIn contrast to these polynomial bounds, some drawing styles may exhibit exponential growth in their areas, implying that these styles may be suitable only for small graphs. An example is upward planar drawing of planar directed acyclic graphs, where the area of an n-vertex drawing may be proportional to 2n in the worst case.[15] Even plane trees may require exponential area, if they are to be drawn with straight edges that preserve a fixed cyclic order around each vertex and must be equally spaced around the vertex.[16]
References
edit- ^ Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs (1st ed.), Prentice Hall, pp. 14–15, ISBN 0133016153.
- ^ Dolev, Danny; Leighton, Tom; Trickey, Howard (1984), "Planar embedding of planar graphs" (PDF), Advances in Computing Research, 2: 147–161
- ^ de Fraysseix, Hubert; Pach, János; Pollack, Richard (1988), "Small sets supporting Fary embeddings of planar graphs", Twentieth Annual ACM Symposium on Theory of Computing, pp. 426–433, doi:10.1145/62212.62254, ISBN 0-89791-264-0, S2CID 15230919.
- ^ Schnyder, Walter (1990), "Embedding planar graphs on the grid", Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138–148.
- ^ Crescenzi, P.; Di Battista, G.; Piperno, A. (1992), "A note on optimal area algorithms for upward drawings of binary trees", Computational Geometry Theory & Applications, 2 (4): 187–200, doi:10.1016/0925-7721(92)90021-J, MR 1196545.
- ^ Garg, Ashim; Goodrich, Michael T.; Tamassia, Roberto (1996), "Planar upward tree drawings with optimal area", International Journal of Computational Geometry & Applications, 6 (3): 333–356, doi:10.1142/S0218195996000228, MR 1409650.
- ^ Chan, T. M. (2002), "A near-linear area bound for drawing binary trees", Algorithmica, 34 (1): 1–13, doi:10.1007/s00453-002-0937-x, MR 1912924, S2CID 5122671.
- ^ Chan, Timothy M.; Goodrich, Michael T.; Kosaraju, S. Rao; Tamassia, Roberto (2002), "Optimizing area and aspect ratio in straight-line orthogonal tree drawings", Computational Geometry Theory & Applications, 23 (2): 153–162, doi:10.1016/S0925-7721(01)00066-9, MR 1922928.
- ^ Garg, Ashim; Rusu, Adrian (2004), "Straight-line drawings of binary trees with linear area and arbitrary aspect ratio", Journal of Graph Algorithms and Applications, 8 (2): 135–160, doi:10.7155/jgaa.00086, MR 2164808.
- ^ Garg, Ashim; Rusu, Adrian (2007), "Area-efficient planar straight-line drawings of outerplanar graphs", Discrete Applied Mathematics, 155 (9): 1116–1140, doi:10.1016/j.dam.2005.12.008, MR 2321019.
- ^ Di Battista, Giuseppe; Frati, Fabrizio (2009), "Small area drawings of outerplanar graphs", Algorithmica, 54 (1): 25–53, doi:10.1007/s00453-007-9117-3, MR 2496664, S2CID 2814656.
- ^ Biedl, Therese (2002), "Drawing outer-planar graphs in O(n log n) area", Graph Drawing:10th International Symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002, Revised Papers, Lecture Notes in Computer Science, vol. 2528, Springer, pp. 54–65, doi:10.1007/3-540-36151-0_6, MR 2063411.
- ^ Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe; Montecchiani, Fabrizio (2013), "Area requirement of graph drawings with few crossings per edge", Computational Geometry Theory & Applications, 46 (8): 909–916, doi:10.1016/j.comgeo.2013.03.001, MR 3061453.
- ^ Frati, Fabrizio (2011), "Improved lower bounds on the area requirements of series–parallel graphs", Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, pp. 220–225, doi:10.1007/978-3-642-18469-7_20, MR 2781267.
- ^ Di Battista, Giuseppe; Tamassia, Roberto; Tollis, Ioannis G. (1992), "Area requirement and symmetry display of planar upward drawings", Discrete and Computational Geometry, 7 (4): 381–401, doi:10.1007/BF02187850, MR 1148953.
- ^ Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Nöllenburg, Martin (2013), "Drawing trees with perfect angular resolution and polynomial area", Discrete and Computational Geometry, 49 (2): 157–182, arXiv:1009.0581, doi:10.1007/s00454-012-9472-y, MR 3017904, S2CID 5000871.