In
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 ...
styles that represent the
edges of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
by
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 ...
s (sequences of
line segment
In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...
s connected at bends), it is desirable to minimize the number of bends per edge (sometimes called the curve complexity)
[.] or the total number of bends in a drawing.
[.] Bend minimization is the
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
ic problem of finding a drawing that minimizes these quantities.
Eliminating all bends
The prototypical example of bend minimization is
Fáry's theorem, which states that every
planar graph
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 cro ...
can be drawn with no bends, that is, with all its edges drawn as straight line segments.
Drawings of a graph in which the edges are both bendless and axis-aligned are sometimes called ''rectilinear drawings'', and are one way of constructing
RAC drawings in which all crossings are at right angles.
However, it is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
to determine whether a
planar graph
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 cro ...
has a planar rectilinear drawing, and NP-complete to determine whether an arbitrary graph has a rectilinear drawing that allows crossings.
[.]
Bend minimization
showed that bend minimization of
orthogonal drawings of planar graphs, in which the vertices are placed in an
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 ...
and the edges are drawn as axis-aligned polylines, could be performed in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
by translating the problem into one of
minimum-cost network flow. However, if the planar embedding of the graph may be changed, then bend minimization becomes NP-complete, and must instead be solved by techniques such as
integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...
that do not guarantee both a fast runtime and an exact answer.
Few bends per edge
Many graph drawing styles allow bends, but only in a limited way: the curve complexity of these drawings (the maximum number of bends per edge) is bounded by some fixed constant. Allowing this constant to grow larger can be used to improve other aspects of the drawing, such as its
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 ...
.
Alternatively, in some cases, a drawing style may only be possible when bends are allowed; for instance, not every graph has a
RAC drawing (a drawing with all crossings at right angles) with no bends, or with curve complexity two, but every graph has such a drawing with curve complexity three.
[.]
References
{{reflist
Graph drawing