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 graph (discrete mathematics), graphs arising from applications such ...
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 discret ...
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 line (mathematics), straight line that is bounded by two distinct endpoints (its extreme points), and contains every Point (geometry), point on the line that is between its endpoints. It is a special c ...
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 Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
ic problem of finding a drawing that minimizes these quantities.
Eliminating all bends
The prototypical example of bend minimization is
Fáry's theorem
In the mathematical field of graph theory, Fáry's theorem states that any simple graph, simple, planar graph can be Graph drawing, drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as ...
, which states that every
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
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 drawing
In graph drawing, a RAC drawing of a Graph (discrete mathematics), graph is a drawing in which the vertices are represented as points, the edges are represented as straight line segments or polylines, at most two edges cross at any point, and when ...
s in which all crossings are at right angles.
However, it is
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
to determine whether a
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
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 (group), lattice in the Euclidean space whose lattice points are tuple, -tuples of integers. The two-dimensional integer lattice is also called the s ...
and the edges are drawn as axis-aligned polylines, could be performed in
polynomial time
In theoretical 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 p ...
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 measure of a region's size on a 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 surface or the boundary of a three-di ...
.
Alternatively, in some cases, a drawing style may only be possible when bends are allowed; for instance, not every graph has a
RAC drawing
In graph drawing, a RAC drawing of a Graph (discrete mathematics), graph is a drawing in which the vertices are represented as points, the edges are represented as straight line segments or polylines, at most two edges cross at any point, and when ...
(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
NP-complete problems