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

Polynomial bounds

For straight-line drawings of planar graphs 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 trees, and trees of bounded degree more generally, have drawings with linear or near-linear area, depending on the drawing style. Every outerplanar graph 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 graphs requires an area larger than n by a superpolylogarithmic factor, even if edges can be drawn as polylines.

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 2ⁿ in the worst case. 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.