General-Position Drawings and Crossing Number

Drawings and Crossings

A drawing represents vertices by distinct points of the plane and edges by arcs joining their endpoints. It lets us ask how many intersections are unavoidable when the graph is represented in the plane. To count those intersections reliably, we first specify what counts as a drawing and remove degeneracies such as tangencies and several edges passing through the same point.

Definition: A drawing of a finite simple graph \(G=(V,E)\) assigns a distinct point of the plane to each vertex and a simple arc to each edge, joining the points assigned to its endpoints. An arc is simple if it does not pass through the same point twice. Edge interiors do not contain vertices. A drawing is in general position if edge interiors meet only at finitely many points, every such meeting is a transverse crossing of exactly two edge interiors, and no three edge interiors meet at one point. A crossing is one such intersection point; its two edges are necessarily distinct. The crossing number \(\operatorname{cr}(G)\) is the minimum number of crossings over all general-position drawings of \(G\).

Here “transverse” means that near the intersection the two arcs pass from one side of each other to the other; they do not merely touch and turn away. Crossings are counted as points, not just as pairs of edges. Thus, if two edge interiors meet at three distinct points, that drawing has three crossings from that pair. General position prevents a single point from being counted for three or more edges.

Some conventions additionally require edges with a common endpoint not to cross again in their interiors. We do not need that extra condition here: our examples have no such intersections, and the definition above states exactly which intersections are counted. A drawing with no crossings is a crossing-free drawing, so \(\operatorname{cr}(G)=0\) precisely when \(G\) has a crossing-free drawing.

Normalizing a Drawing

To normalize a drawing is to arrange that its intersections satisfy the general-position conditions, so that a crossing count is unambiguous. For polygonal drawings, the usual procedure is to make small local changes: replace tangencies by transverse intersections or by disjoint arcs, separate distinct intersections that coincide, and move bends slightly so that no vertex lies on an unrelated edge. The changes can be confined to small regions around the degeneracies. When selecting a resolution, one should avoid introducing unnecessary crossings.

This is a geometric procedure, not a claim that every chosen perturbation preserves the crossing count. A tangency, for example, may be resolved in different ways, and one resolution can have more intersections than another. For a proposed drawing, the safe practice is to specify the arcs or coordinates, check all edge pairs, and count the resulting distinct intersection points. Once a drawing is in general position, that count is well-defined.

Record the graph and the drawing.
List \(V\) and \(E\), then specify vertex locations and, for polygonal edges, the bend points in order.

Check for degeneracies.
Confirm that no edge interior passes through a vertex, that intersections are finite and transverse, and that no three edge interiors share a point.

List intersecting edge pairs.
For each pair, identify every intersection in the interiors of both edges. Shared endpoints are not crossings.

Count points and verify.
Add the intersection points, checking that distinct points are not accidentally counted as one and that every edge pair has been considered.

For straight-line drawings, a determinant test makes the pair check exact. For points \(A=(x_A,y_A)\), \(B=(x_B,y_B)\), and \(C=(x_C,y_C)\), define the orientation determinant

\operatorname{orient}(A,B,C) =(x_B-x_A)(y_C-y_A)-(y_B-y_A)(x_C-x_A).

Its sign tells which side of the directed line \(AB\) contains \(C\). Suppose the four endpoints \(A,B,C,D\) are distinct and no three are collinear. The segments \(AB\) and \(CD\) cross properly in their interiors exactly when

\operatorname{orient}(A,B,C)\operatorname{orient}(A,B,D)<0 \quad\text{and}\quad \operatorname{orient}(C,D,A)\operatorname{orient}(C,D,B)<0.

Justification. The first strict inequality says \(C\) and \(D\) lie on opposite sides of the line through \(A,B\); the second says \(A\) and \(B\) lie on opposite sides of the line through \(C,D\). The two supporting lines therefore intersect, and each segment contains that intersection in its interior. Conversely, if the segments cross in their interiors, each line meets the other segment between its endpoints, so the endpoints of that segment lie on opposite sides of the line. Neither product can be zero because no three endpoints are collinear. \(\square\)

Examples of Crossing Counts

Worked Example: The Straight-Line Drawing of \(K_4\)

Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\), so \(G=K_4\). Place the vertices at \(1=(0,0)\), \(2=(2,0)\), \(3=(2,2)\), and \(4=(0,2)\), and draw every edge as a straight segment.

The four edges \(12,23,34,41\) form the boundary of the square. Their interiors do not intersect one another. The other two edges, \(13\) and \(24\), are its diagonals. Their endpoints lie on opposite sides of each other’s supporting line: for \(13\), the line is \(y=x\), and \(2=(2,0)\) and \(4=(0,2)\) lie on opposite sides; for \(24\), the line is \(x+y=2\), and \(1=(0,0)\) and \(3=(2,2)\) lie on opposite sides. Thus the diagonals meet in their interiors.

Solving \(y=x\) and \(x+y=2\) gives \(x=1\), \(y=1\). The two diagonals meet at \((1,1)\), so this drawing has exactly one crossing.

Check: the boundary edges meet only at their shared endpoints, and neither diagonal meets a boundary edge in its interior. The only crossing is between \(13\) and \(24\). Hence the count is \(1\), not \(2\): the two diagonals form one intersection point.

Worked Example: Testing Two Segments Exactly

Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\) and \(E=\{12,34\}\). Place \(1=(0,0)\), \(2=(4,0)\), \(3=(1,-1)\), and \(4=(3,1)\), and draw the two edges as straight segments. The vertices are distinct, and the edges have no common endpoint.

For \(A=1\), \(B=2\), \(C=3\), and \(D=4\), the orientation values are

\operatorname{orient}(1,2,3)=4(-1)-0(1)=-4,\qquad \operatorname{orient}(1,2,4)=4(1)-0(3)=4,

and

\operatorname{orient}(3,4,1)=2(1)-2(-1)=4,\qquad \operatorname{orient}(3,4,2)=2(1)-2(3)=-4.

The products are \((-4)(4)=-16<0\) and \(4(-4)=-16<0\), so the segments cross properly. Directly, the segment \(12\) lies on \(y=0\); the segment \(34\) has direction vector \((2,2)\), so its points are \((1+2t,-1+2t)\) for \(0\le t\le1\). Setting \(y=0\) gives \(t=\frac12\), hence the intersection is \((2,0)\). It is interior to both segments.

Check: the graph has just two edges, and they meet at that single interior point. The crossing count is therefore \(1\).

Worked Example: One Pair Can Cross More Than Once

Let \(G=(V,E)\) again have \(V=\{1,2,3,4\}\) and \(E=\{12,34\}\). Put \(1=(0,0)\), \(2=(4,0)\), \(3=(1,-1)\), and \(4=(3,1)\). Draw edge \(12\) as the horizontal segment from \(1\) to \(2\). Draw edge \(34\) as the polygonal arc with successive points \((1,-1)\), \((1,1)\), \((3,-1)\), and \((3,1)\).

The first vertical piece of \(34\) meets \(y=0\) at \((1,0)\). The middle piece runs from \((1,1)\) to \((3,-1)\), so its points are \((1+2t,1-2t)\), where \(0\le t\le1\). Setting \(1-2t=0\) gives \(t=\frac12\) and the intersection \((2,0)\). The final vertical piece meets \(y=0\) at \((3,0)\). All three points lie inside both edges, and they are distinct. Thus this drawing is in general position and has three crossings, all from the same pair of edges.

If edge \(34\) is instead drawn as the straight segment from \((1,-1)\) to \((3,1)\), it meets \(12\) at \((2,0)\) only. This second drawing has one crossing. The first count describes that particular drawing; it does not establish the crossing number.

Check: in the polygonal drawing the crossing coordinates have \(x\)-values \(1\), \(2\), and \(3\), so no two intersections coincide. In the straight-line drawing the equation for \(34\) is \(y=x-2\); setting \(y=0\) gives \(x=2\), confirming exactly one crossing.

The Crossing Number Is a Minimum

Proposition: Every finite simple graph has a well-defined crossing number: there is a general-position drawing whose number of crossings equals \(\operatorname{cr}(G)\).

Proof. A finite simple graph has at least one drawing: place its finitely many vertices at distinct points and join the endpoints of each edge by polygonal arcs, choosing bends so that the drawing is in general position. Thus the set \(S\) of crossing counts of general-position drawings is nonempty. Every member of \(S\) is a nonnegative integer. By the well-ordering principle, every nonempty set of nonnegative integers has a least element; call it \(k\). Since \(k\in S\), some drawing has exactly \(k\) crossings. By definition this least possible count is \(\operatorname{cr}(G)\), so the minimum is attained. This also covers the graph with no edges: any placement of its vertices has zero crossings, and no crossing count can be negative. \(\square\)

The proposition explains why the word minimum is appropriate: the crossing number is not merely a lower bound approached by a sequence of drawings. It is the count in at least one drawing. But computing that minimum is a separate problem. Finding a drawing with \(k\) crossings proves only \(\operatorname{cr}(G)\le k\); to prove equality one must also rule out every drawing with fewer crossings.

Common Pitfalls

Confusing a drawing’s count with the crossing number. In the third example, the specified polygonal drawing has three crossings, while another drawing of the same graph has one. Reporting “the crossing number is three” from the first drawing would be wrong: it would confuse a count in one drawing with a minimum over all drawings.

Counting pairs instead of intersection points. Two edges that cross at three distinct points contribute three crossings under the definition used here, not one. Conversely, several pairs meeting at a single triple point do not form a general-position drawing; separate the intersections before using a crossing count.

Counting shared endpoints. Edges \(12\) and \(13\) meet at vertex \(1\), but that shared endpoint is not a crossing. A crossing must lie in the interior of each of the two edges.

Ignoring strictness in the segment test. The determinant products must be strictly negative for a proper crossing. A zero product signals a degeneracy such as collinearity or an endpoint lying on the other segment; it does not certify an interior crossing. Resolve such cases before counting crossings in a general-position drawing.

Check Your Understanding

Use the definitions and determinant test to justify each answer.

In a general-position drawing, two edge interiors meet at four distinct points. How many crossings do they contribute?
Let \(V=\{1,2,3\}\) and \(E=\{12,23\}\). Draw the two edges as straight segments with vertices at \((0,0)\), \((1,0)\), and \((2,0)\). Is this a general-position drawing? What should be changed before applying the crossing count?
Explain why a drawing with seven crossings proves \(\operatorname{cr}(G)\le7\), but does not by itself prove \(\operatorname{cr}(G)=7\).
For endpoints \(A=(0,0)\), \(B=(2,0)\), \(C=(1,-1)\), and \(D=(1,1)\), compute the four orientation determinants and use their signs to decide whether \(AB\) and \(CD\) cross properly.