graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, car ...

, 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 In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or gri ...

, the area of the drawing may be defined as the

area Area is the quantity that expresses the extent of a region on the plane or on a curved surface. The area of a plane region or ''plane area'' refers to the area of a shape or planar lamina, while ''surface area'' refers to the area of an open su ...

of the smallest axis-aligned

bounding box In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure ...

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..

Polynomial bounds

For straight-line drawings of

planar graphs In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

with ''n'' vertices, the optimal worst-case bound on the area of a drawing is Θ(''n''²). The nested triangles graph requires this much area no matter how it is embedded, and several methods are known that can draw planar graphs with at most quadratic area.

Binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binar ...

s, and trees of bounded degree more generally, have drawings with linear or near-linear area, depending on the drawing style. Every

outerplanar graph In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two fo ...

has a straight-line outerplanar drawing with area subquadratic in its number of vertices, If bends or crossings are allowed, then outerplanar graphs have drawings with near-linear area. However, drawing

series–parallel graph In graph theory, series–parallel graphs are graphs with two distinguished vertices called ''terminals'', formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits. Definition and t ...

s requires an area larger than ''n'' multiplied by a superpolylogarithmic factor, even if edges can be drawn as

polyline In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points (A_1, A_2, \dots, A_n) called its vertices. The curve itself consists of the line segments co ...

Exponential bounds

In contrast to these polynomial bounds, some drawing styles may exhibit

exponential growth Exponential growth is a process that increases quantity over time. It occurs when the instantaneous rate of change (that is, the derivative) of a quantity with respect to time is proportional to the quantity itself. Described as a function, a ...

in their areas, implying that these styles may be suitable only for small graphs. An example is

upward planar drawing In graph drawing, an upward planar drawing of a directed acyclic graph is an embedding of the graph into the Euclidean plane, in which the edges are represented as non-crossing monotonic upwards curves. That is, the curve representing each ed ...

of planar

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one v ...

s, where the area of an ''n''-vertex drawing may be proportional to 2^''n'' in the worst case. Even

plane tree ''Platanus'' is a genus consisting of a small number of tree species native to the Northern Hemisphere. They are the sole living members of the family Platanaceae. All mature members of ''Platanus'' are tall, reaching in height. All except ...

s may require exponential area, if they are to be drawn with straight edges that preserve a fixed

cyclic order In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "". One does not say that east is "more clockwise" than west. In ...

around each vertex and must be equally spaced around the vertex..

References

{{reflist Area Graph drawing