In
graph drawing, the area used by a drawing is a commonly used way of measuring its quality.
Definition
For 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
For 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
In 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
^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,
ISBN0133016153.
^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,
MR1196545.
^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,
MR1409650.
^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,
MR2063411.
^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,
MR3061453.
^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,
MR2781267.