![]()
Part II
Crossing Number Variants
![]()
Chapter 5
The Rectilinear Crossing Number: Rectilinear and Pseudolinear Drawings
5.1 A First Look
Recall that in a rectilinear (also called geometric or straight-line) drawing of a graph, edges are realized by straight-line segments (without bends). The rectilinear crossing number, , of a graph G is the smallest number of crossings in any rectilinear drawing of G. If , then G is planar, and, as it turns out, the reverse is also true, a result known by many names.
Theorem 5.1 (Fary’s (Wagner’s, Stein’s) Theorem [132, 320, 347]). Every planar graph has a rectilinear embedding.
We use a simple geometric fact: every polygon of length at most 5 is starshaped; that is, it contains a point in its interior which can see all points in the polygon, in the sense that it can be connected by a straight-line segment—lying within the polygon—to any other point inside the polygon. (Triangulate the polygon; there are at most three triangles, so there must be a vertex belonging to all triangles; that vertex, and points in a wedge close to it will do.)
Proof. We prove by induction on the number of vertices that every plane graph has a rectilinear embedding with the same rotation scheme. The result is clear for graphs with n ≤ 3 vertices, so we can assume that there are at least 4 vertices. By Euler’s formula, Corollary A.5, there is a vertex v of degree at most 5. Inductively find a rectilinear embedding of G − v. We need to argue that we can add v back into the face from which it was removed (the face still exists in the rectilinear embedding, since we maintained the rotation system). But this is possible by the geometric fact we outlined before the proof. □
The proof establishes more than we claimed: the rectilinear embedding we construct is isomorphic to the original embedding. A drawing which is isomorphic to a rectilinear drawing is called stretchable. So Fary’s theorem states that every plane embedding is stretchable. If the graph is 3-connected, we can even guarantee that the rectilinear embedding is strictly convex, that is, all inner faces are strictly convex polygons (all inner angles strictly less than π).1 This is Tutte’s celebrated spring theorem.
Theorem 5.2 (Tutte [338]). Every plane, 3-connected graph is isomorphic to a strictly convex, rectilinear embedding.
Tutte’s result implies Fary’s theorem (Exercise (5.1)), but its proof is more intricate; we recommend [333]. Does Fary’s Theorem remain true in the presence of crossings? The answer is a qualified yes.
Theorem 5.3 (Bienstock and Dean [65]). We have if cr(G) ≤ 3.
The strategy for the proof is simple: add crossing-free edges to G to ensure that G without the crossing edges is a plane, 3-connected graph. Take a strictly convex embedding of this graph, and reinsert the crossing edges. This approach works for cr(G) = 1 (c...
