A straight-line drawing embeds graph vertices as points in the plane and represents every edge by a straight line segment between its endpoints. Restricting edges to segments simplifies intersection testing, but can require more crossings than curved edges. section 15.5 section 15.3.2
A practical segment-intersection test proceeds in stages:
- Screen out pairs whose axis-aligned bounding boxes do not overlap; separated x- or y-projections prove that the segments cannot cross. section 15.4.1
- For remaining pairs, compute where the supporting lines meet and verify that the intersection lies within both segments. section 15.4.1
- Implement the vector method with scaling factors h and g, accepting 0 ≤ h ≤ 1 and 0 ≤ g ≤ 1 while excluding shared endpoints when appropriate. section 15.4.1
The restriction matters when minimizing crossings. The rectilinear crossing number is never below the unrestricted crossing number; some graphs therefore need fewer intersections when edges may use Bézier curves. section 15.3.2 section 16.1.2
A graph whose restriction costs crossings
For one graph, a straight-line drawing requires 12 intersections, whereas a curved-edge embedding reduces the count to 4. Moving vertices cannot improve the straight-line result without abandoning the segment restriction. section 15.3.2
Figure 15.16 Examples of non-intersecting segments: the bounding-box check can only rule out an intersection, but cannot confirm it.
Use the figure to distinguish bounding-box rejection from actual segment intersection: overlapping boxes do not prove that segments cross. section 15.4.1
