Graph Drawing

A graph drawing is a representation of a graph in a geometric space in which distinct vertices are represented by distinct points and each graph edge is represented by a simple curve joining the points corresponding to its endpoints, with no other graph vertex in its interior. A general graph drawing may have graph crossings between edges that do not share an endpoint. This distinguishes a graph drawing from a graph embedding, in which edges intersect only at common endpoints.

The abstract graph specifies which pairs of vertices are adjacent, but not the positions of the points or the shapes of the curves in a drawing. Consequently, the same graph can have many different graph drawings. Drawings are usually made in the plane, although drawings in three or more dimensions are also used.

Special types of graph drawings impose additional geometric conditions. In a good drawing, each pair of edges meets at most once, either at a common endpoint or at a proper graph crossing, and no three edges meet away from vertices. In a circular drawing, all vertices lie on a circle; in a straight line drawing, every graph edge is a line segment; and in an integral drawing, graph edge lengths are integers. A drawing in the plane whose edges meet only at common endpoints is a planar graph embedding. Replacing graph crossings by vertices yields a graph planarization. Graph drawing algorithms seek informative and legible layouts using criteria such as the numbers of graph crossings and bends, drawing area, graph edge lengths, angular resolution, and symmetry (Di Battista et al. 1998, Tamassia 2000).

Graphs can be drawn in the Wolfram Language using Graph[...], with layouts specified using the option GraphLayout.

The variation in graph edge lengths can be quantified by the infimum of the longest-to-shortest ratio over planar straight line drawings. Sabaei et al. (2026) proved that its largest value on -vertex 2-trees is , where denotes big-Theta notation. The explicit upper bound holds for this infimum on every -vertex graph of treewidth at most two with at least one graph edge, for . Here is the floor function.