To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.

Area (graph drawing)

From Wikipedia, the free encyclopedia

In graph drawing, the area used by a drawing is a commonly used way of measuring its quality.


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]


  1. ^ 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.
  2. ^ Dolev, Danny; Leighton, Tom; Trickey, Howard (1984), "Planar embedding of planar graphs" (PDF), Advances in Computing Research, 2: 147–161
  3. ^ 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.
  4. ^ Schnyder, Walter (1990), "Embedding planar graphs on the grid", Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138–148.
  5. ^ 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.
  6. ^ 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.
  7. ^ 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.
  8. ^ 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.
  9. ^ 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.
  10. ^ 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.
  11. ^ 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.
  12. ^ 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, 2528, Springer, pp. 54–65, doi:10.1007/3-540-36151-0_6, MR 2063411.
  13. ^ 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.
  14. ^ 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, 6502, pp. 220–225, doi:10.1007/978-3-642-18469-7_20, MR 2781267.
  15. ^ 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.
  16. ^ 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.
This page was last edited on 25 July 2021, at 18:12
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.