Bend minimization
{{Short description|Graph drawing with few edge bends}}
In graph drawing styles that represent the edges of a graph by polylines (sequences of line segments connected at bends), it is desirable to minimize the number of bends per edge (sometimes called the curve complexity){{citation
| last1 = Di Giacomo | first1 = Emilio
| last2 = Didimo | first2 = Walter
| last3 = Liotta | first3 = Giuseppe
| last4 = Meijer | first4 = Henk
| doi = 10.1007/s00224-010-9275-6
| issue = 3
| journal = Theory of Computing Systems
| mr = 2822838
| pages = 565–575
| title = Area, curve complexity, and crossing resolution of non-planar graph drawings
| volume = 49
| year = 2011}}. or the total number of bends in a drawing.{{citation
| last1 = Di Battista | first1 = Giuseppe
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
| last3 = Tamassia | first3 = Roberto | author3-link = Roberto Tamassia
| last4 = Tollis | first4 = Ioannis G.
| edition = 1st
| isbn = 978-0133016154
| pages = 15–16
| publisher = Prentice Hall
| title = Graph Drawing: Algorithms for the Visualization of Graphs
| year = 1998}}. Bend minimization is the algorithmic problem of finding a drawing that minimizes these quantities.{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, p. 145.{{citation
| last = Purchase | first = Helen | authorlink = Helen Purchase
| contribution = Which aesthetic has the greatest effect on human understanding?
| doi = 10.1007/3-540-63938-1_67
| pages = 248–261
| series = Lecture Notes in Computer Science
| title = Graph Drawing: 5th International Symposium, GD '97 Rome, Italy, September 18–20, 1997, Proceedings
| volume = 1353
| year = 1997| isbn = 978-3-540-63938-1 | doi-access = free
}}.
Eliminating all bends
The prototypical example of bend minimization is Fáry's theorem, which states that every planar graph can be drawn with no bends, that is, with all its edges drawn as straight line segments.{{harvtxt|Di Battista|Eades|Tamassia|Tollis|1998}}, p. 140.
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 to determine whether a planar graph has a planar rectilinear drawing,{{citation
| last1 = Garg | first1 = Ashim
| last2 = Tamassia | first2 = Roberto | author2-link = Roberto Tamassia
| doi = 10.1137/S0097539794277123
| issue = 2
| journal = SIAM Journal on Computing
| mr = 1861292
| pages = 601–625
| title = On the computational complexity of upward and rectilinear planarity testing
| volume = 31
| year = 2001}}. and NP-complete to determine whether an arbitrary graph has a rectilinear drawing that allows crossings.{{citation
| last1 = Eades | first1 = Peter | author1-link = Peter Eades
| last2 = Hong | first2 = Seok-Hee | author2-link = Seok-Hee Hong
| last3 = Poon | first3 = Sheung-Hung
| contribution = On rectilinear drawing of graphs
| doi = 10.1007/978-3-642-11805-0_23
| mr = 2680455
| pages = 232–243
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers
| volume = 5849
| year = 2010| isbn = 978-3-642-11804-3 | doi-access = free
}}.
Bend minimization
{{harvtxt|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.{{citation
| last = Tamassia | first = Roberto | authorlink = Roberto Tamassia
| doi = 10.1137/0216030
| issue = 3
| journal = SIAM Journal on Computing
| mr = 889400
| pages = 421–444
| title = On embedding a graph in the grid with the minimum number of bends
| volume = 16
| year = 1987}}.{{citation
| last1 = Cornelsen | first1 = Sabine
| last2 = Karrenbauer | first2 = Andreas
| doi = 10.7155/jgaa.00265
| issue = 3
| journal = Journal of Graph Algorithms and Applications
| mr = 2983428
| pages = 635–650
| title = Accelerated bend minimization
| volume = 16
| year = 2012| doi-access = free
}}. 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.{{citation
| last1 = Mutzel | first1 = Petra | author1-link = Petra Mutzel
| last2 = Weiskircher | first2 = René
| contribution = Bend minimization in orthogonal drawings using integer programming
| doi = 10.1007/3-540-45655-4_52
| pages = 484–493
| series = Lecture Notes in Computer Science
| title = Computing and Combinatorics: 8th Annual International Conference, COCOON 2002, Singapore, August 15–17, 2002, Proceedings
| volume = 2387
| year = 2002| citeseerx = 10.1.1.138.1513| isbn = 978-3-540-43996-7 }}.
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. 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.{{citation
| last1 = Didimo | first1 = Walter
| last2 = Eades | first2 = Peter | author2-link = Peter Eades
| last3 = Liotta | first3 = Giuseppe
| contribution = Drawing graphs with right angle crossings
| doi = 10.1007/978-3-642-03367-4_19
| pages = 206–217
| series = Lecture Notes in Computer Science
| title = Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings
| volume = 5664
| year = 2009| title-link = SWAT and WADS conferences
| isbn = 978-3-642-03366-7
}}.