Crossing Numbers of Graphs

Marcus Schaefer

• Publisher: CRC Press
• Year: 2018
• ISBN:
  9781351648448
• Edition: 1
• Topic: Matemáticas
• Subtopic: Conteo y numeración

Crossing Numbers of Graphs is the first book devoted to the crossing number, an increasingly popular object of study with surprising connections. The field has matured into a large body of work, which includes identifiable core results and techniques. The book presents a wide variety of ideas and techniques in topological graph theory, discrete geometry, and computer science.

The first part of the text deals with traditional crossing number, crossing number values, crossing lemma, related parameters, computational complexity, and algorithms. The second part includes the rich history of alternative crossing numbers, the rectilinear crossing number, the pair crossing number, and the independent odd crossing number.It also includes applications of the crossing number outside topological graph theory.

• Aimed at graduate students and professionals in both mathematics and computer science
• The first book of its kind devoted to the topic
• Authored by a noted authority in crossing numbers

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, $\overline{\text{cr}}\left(G\right)$, of a graph G is the smallest number of crossings in any rectilinear drawing of G. If $\overline{\text{cr}}\left(G\right)=0$, 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 π).¹ 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 $\overline{\text{cr}}\left(G\right)=\text{cr}\left(G\right)$ 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...