Area (graph drawing)
{{Short description|Size of bounding box of graph drawing}}
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.{{citation
| last1 = Di Battista | first1 = Giuseppe
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
| last3 = Tamassia | first3 = Roberto | author3-link = Roberto Tamassia
| last4 = Tollis | first4 = Ioannis G.
| edition = 1st
| isbn = 0133016153
| pages = 14–15
| publisher = Prentice Hall
| title = Graph Drawing: Algorithms for the Visualization of Graphs
| year = 1998}}.
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,{{citation
| last1 = Dolev | first1 = Danny | author1-link = Danny Dolev
| last2 = Leighton | first2 = Tom | author2-link = F. Thomson Leighton
| last3 = Trickey | first3 = Howard
| journal = Advances in Computing Research
| pages = 147–161
| title = Planar embedding of planar graphs
| url = http://noodle.cs.huji.ac.il/~dolev/pubs/planar-embed.pdf
| volume = 2
| year = 1984}} and several methods are known that can draw planar graphs with at most quadratic area.{{citation
| last1 = de Fraysseix | first1 = Hubert
| last2 = Pach | first2 = János | author2-link = János Pach
| last3 = Pollack | first3 = Richard | author3-link = Richard M. Pollack
| contribution = Small sets supporting Fary embeddings of planar graphs
| doi = 10.1145/62212.62254
| isbn = 0-89791-264-0
| pages = 426–433
| title = Twentieth Annual ACM Symposium on Theory of Computing
| year = 1988| s2cid = 15230919
| doi-access = free
}}.{{citation
| last = Schnyder | first = Walter
| contribution = Embedding planar graphs on the grid
| pages = 138–148
| title = Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA)
| url = http://portal.acm.org/citation.cfm?id=320176.320191
| year = 1990| isbn = 978-0-89871-251-3
}}. Binary trees, and trees of bounded degree more generally, have drawings with linear or near-linear area, depending on the drawing style.{{citation
| last1 = Crescenzi | first1 = P.
| last2 = Di Battista | first2 = G.
| last3 = Piperno | first3 = A.
| doi = 10.1016/0925-7721(92)90021-J
| issue = 4
| journal = Computational Geometry Theory & Applications
| mr = 1196545
| pages = 187–200
| title = A note on optimal area algorithms for upward drawings of binary trees
| volume = 2
| year = 1992| doi-access =
}}.{{citation
| last1 = Garg | first1 = Ashim
| last2 = Goodrich | first2 = Michael T. | author2-link = Michael T. Goodrich
| last3 = Tamassia | first3 = Roberto
| doi = 10.1142/S0218195996000228
| issue = 3
| journal = International Journal of Computational Geometry & Applications
| mr = 1409650
| pages = 333–356
| title = Planar upward tree drawings with optimal area
| volume = 6
| year = 1996}}.{{citation
| last = Chan | first = T. M. | authorlink = Timothy M. Chan
| doi = 10.1007/s00453-002-0937-x
| issue = 1
| journal = Algorithmica
| mr = 1912924
| pages = 1–13
| title = A near-linear area bound for drawing binary trees
| volume = 34
| year = 2002| s2cid = 5122671 }}.{{citation
| last1 = Chan | first1 = Timothy M. | author1-link = Timothy M. Chan
| last2 = Goodrich | first2 = Michael T. | author2-link = Michael T. Goodrich
| last3 = Kosaraju | first3 = S. Rao | author3-link = S. Rao Kosaraju
| last4 = Tamassia | first4 = Roberto | author4-link = Roberto Tamassia
| doi = 10.1016/S0925-7721(01)00066-9
| issue = 2
| journal = Computational Geometry Theory & Applications
| mr = 1922928
| pages = 153–162
| title = Optimizing area and aspect ratio in straight-line orthogonal tree drawings
| volume = 23
| year = 2002| doi-access =
}}.{{citation
| last1 = Garg | first1 = Ashim
| last2 = Rusu | first2 = Adrian
| doi = 10.7155/jgaa.00086
| issue = 2
| journal = Journal of Graph Algorithms and Applications
| mr = 2164808
| pages = 135–160
| title = Straight-line drawings of binary trees with linear area and arbitrary aspect ratio
| volume = 8
| year = 2004| doi-access = free
}}. Every outerplanar graph has a straight-line outerplanar drawing with area subquadratic in its number of vertices,{{citation
| last1 = Garg | first1 = Ashim
| last2 = Rusu | first2 = Adrian
| doi = 10.1016/j.dam.2005.12.008
| issue = 9
| journal = Discrete Applied Mathematics
| mr = 2321019
| pages = 1116–1140
| title = Area-efficient planar straight-line drawings of outerplanar graphs
| volume = 155
| year = 2007| doi-access = free
}}.{{citation
| last1 = Di Battista | first1 = Giuseppe
| last2 = Frati | first2 = Fabrizio
| doi = 10.1007/s00453-007-9117-3
| issue = 1
| journal = Algorithmica
| mr = 2496664
| pages = 25–53
| title = Small area drawings of outerplanar graphs
| volume = 54
| year = 2009| s2cid = 2814656
}}. If bends or crossings are allowed, then outerplanar graphs have drawings with near-linear area.{{citation
| last = Biedl | first = Therese | authorlink = Therese Biedl
| contribution = Drawing outer-planar graphs in O(n log n) area
| doi = 10.1007/3-540-36151-0_6
| mr = 2063411
| pages = 54–65
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Graph Drawing:10th International Symposium, GD 2002, Irvine, CA, USA, August 26–28, 2002, Revised Papers
| volume = 2528
| year = 2002| doi-access = free
| isbn = 978-3-540-00158-4 }}.{{citation
| last1 = Di Giacomo | first1 = Emilio
| last2 = Didimo | first2 = Walter
| last3 = Liotta | first3 = Giuseppe
| last4 = Montecchiani | first4 = Fabrizio
| doi = 10.1016/j.comgeo.2013.03.001
| issue = 8
| journal = Computational Geometry Theory & Applications
| mr = 3061453
| pages = 909–916
| title = Area requirement of graph drawings with few crossings per edge
| volume = 46
| year = 2013| doi-access = free
}}. However, drawing series–parallel graphs requires an area larger than n multiplied by a superpolylogarithmic factor, even if edges can be drawn as polylines.{{citation
| last = Frati | first = Fabrizio
| contribution = Improved lower bounds on the area requirements of series–parallel graphs
| doi = 10.1007/978-3-642-18469-7_20
| mr = 2781267
| pages = 220–225
| series = Lecture Notes in Computer Science
| title = Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21–24, 2010, Revised Selected Papers
| volume = 6502
| year = 2011| doi-access = free
| isbn = 978-3-642-18468-0
}}.
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.{{citation
| last1 = Di Battista | first1 = Giuseppe
| last2 = Tamassia | first2 = Roberto
| last3 = Tollis | first3 = Ioannis G.
| doi = 10.1007/BF02187850
| issue = 4
| journal = Discrete and Computational Geometry
| mr = 1148953
| pages = 381–401
| title = Area requirement and symmetry display of planar upward drawings
| volume = 7
| year = 1992| doi-access = free
}}. 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.{{citation
| last1 = Duncan | first1 = Christian A.
| last2 = Eppstein | first2 = David | author2-link = David Eppstein
| last3 = Goodrich | first3 = Michael T. | author3-link = Michael T. Goodrich
| last4 = Kobourov | first4 = Stephen G.
| last5 = Nöllenburg | first5 = Martin
| doi = 10.1007/s00454-012-9472-y
| issue = 2
| journal = Discrete and Computational Geometry
| mr = 3017904
| pages = 157–182
| title = Drawing trees with perfect angular resolution and polynomial area
| volume = 49
| year = 2013| arxiv = 1009.0581| s2cid = 5000871
}}.