A curve-line drawing represents graph edges with curves instead of straight-line segments. This broader choice can reduce edge intersections, so its crossing number can be smaller than the rectilinear crossing number. section 15.3.2
The technique changes the available embeddings and their trade-offs:
- For graphs with crossing number at most 3, straight-line drawings can achieve the minimum number of crossings. section 15.3.2
- For some graphs, cubic Bézier curves reduce intersections that straight segments cannot avoid. section 15.3.2
- For complete graphs with n ≥ 10, the rectilinear crossing number exceeds the ordinary crossing number. section 15.3.2
Reducing crossings
A graph whose straight-line drawing requires 12 intersections can reach four intersections by moving selected edges to the external face and drawing them as cubic Bézier curves. section 15.3.2
Figure 15.14 The simplest graph for which the rectilinear crossing number is larger than the crossing number. Intersections are highlighted by the little arrows.
Compare the straight-line and curve-based embeddings and inspect where intersections occur. section 15.3.2
Figure 15.15 An alternative minimum crossing embedding for K6: using curves for the edges allows us to keep a more regular layout for the vertices.
Inspect how curved edges preserve a more regular vertex layout while achieving a minimum-crossing embedding for K6. section 15.3.2
