[6] However, it is NP-complete to determine whether a planar graph has a planar rectilinear drawing,[7] and NP-complete to determine whether an arbitrary graph has a rectilinear drawing that allows crossings.
[6] Tamassia (1987) showed that bend minimization of orthogonal drawings of planar graphs, in which the vertices are placed in an integer lattice and the edges are drawn as axis-aligned polylines, could be performed in polynomial time by translating the problem into one of minimum-cost network flow.
[8][9] 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 that do not guarantee both a fast runtime and an exact answer.
[10] 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.