Lemma. Normalization without increasing the point count [cn-0009]
Status: proof-account
Statement. Every admissible drawing [cn-0004] of a finite simple graph can be replaced by a normalized drawing [cn-0008] with no greater crossing count [cn-0005].
Proof. Isolate finitely many marks. Mark the vertices and crossings. On each injectively parameterized edge choose disjoint parameter neighborhoods of its marks, with disjoint closures. The compact remainder of that edge avoids each corresponding mark. Compactness and finiteness therefore allow disjoint closed round disks around the marks, such that all visits to a disk occur inside its chosen parameter neighborhood and nonincident edges avoid the disk.
At an interior mark remove the interval from the first to the last visit to its disk. At an initial vertex remove the initial interval through the last visit; at a terminal vertex remove the final interval from the first visit. The retained pieces are disjoint compact arcs, with distinct boundary endpoints and interiors outside all disks. This use of first and last visits avoids assuming finitely many intersections with a disk boundary.
Give those compact pieces pairwise disjoint open neighborhoods. At each boundary endpoint take a short radial outward spur. A sufficiently small exterior collar connects its tip to a nearby point of the original arc without entering any disk. The resulting connection lies in an open set. Cover its compact image by small balls in that set, subdivide the parameter interval, and replace each short subarc by a straight segment within its ball. This gives a polygonal path with the required endpoints. Subdivide its finite segment arrangement and take a simple graph path to erase loops and overlaps. Disjoint neighborhoods keep the replacements disjoint.
Inside a crossing disk connect the two endpoint pairs by straight chords. Four distinct boundary points give at most one transverse crossing. Inside a vertex disk choose a new vertex off the finitely many lines through pairs of boundary points, and connect all points to it by straight spokes. Assemble the exterior pieces and disk pieces in their original edge order. Each edge is simple, no interior contains a vertex, and every new crossing lies in an old crossing disk. There is at most one crossing per such disk and no third edge there.
Remove adjacent crossings. Suppose \(vu\) and \(vw\) cross at \(x\). In a small disk containing just that crossing, exchange their prefixes from \(v\) and reconnect each exchanged prefix to the appropriate original suffix. The new connections pair adjacent boundary points, so disjoint chords remove the crossing. Outside the disk the two walks use each old open track exactly once in total.
Subdivide their tracks at bends and crossings, and delete closed subwalks until each walk is simple. At a remaining old crossing, either the two tracks belong to different walks, in which case retained passages remain straight through, or both belong to one walk, in which case a new turn can occur only where the other walk and all third edges are absent. The same reasoning applies to meetings with third edges. Thus this simplification adds no crossings or improper meetings. It preserves the abstract endpoints and strictly reduces the point count.
Repeat while an adjacent crossing remains. The nonnegative integer count decreases at every step, so the process terminates. Straightness near the remaining vertices and crossings is preserved. This proves the assertion. The paper discusses the standard ordinary-crossing reduction with reference to Fulek et al. [cn-0049]; the continuous-arc construction is written out in its Appendix A.
Scope of normalization. For the replacement \(D'\), the proved comparison is \(c(D')\leq c(D)\). It does not give \(c(D')\leq c_-(D)\), where \(c_-(D)\) is the independent crossing count [cn-0066]. Thus the lemma justifies prohibiting adjacent crossings when minimizing the ordinary count, but does not prove \(\operatorname {cr}_-(G)=\operatorname {cr}(G)\).
The prefix exchange explains the distinction. In a complete bipartite graph take \(e=a_1b_1\), \(f=a_1b_2\), and \(g=a_2b_1\). If a prefix of \(e\) crossing \(g\) is reassigned to \(f\), that retained crossing changes from adjacent to independent: \(e\) and \(g\) share \(b_1\), whereas \(f\) and \(g\) have no common endpoint. No new crossing point is needed for the number of counted independent crossings to increase. The 2012 reference [cn-0049], p. 760, explicitly distinguishes these two minimization problems.
- Proof dependencies
- Admissibility [cn-0004]; Point count [cn-0005]; Normalized drawings [cn-0008]
- Provenance
- OpenAI, 23 September 2026 [cn-0042], Appendix A, Lemma A.1; reconstructed as a reading account on 9 October 2026. Lean source: LocallyTransverseNormalization.