OctoInformBeta

OpenAI preprint, September 2026 · §2. Sweeps, activity, and exchange graphs

Lemma 2.5: Cubic edge bounds for drawings in general position with distinct first coordinates, including the dense case

A vertex cover controls drawing crossings.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A vertex cover FF of a graph is a designated set of its vertices that meets every edge. The crossing bounds here concern straight-line drawings with such a cover, with constants depending on both the size of the cover and the number of vertices.

Planar points p=(px,py)p=(p_x,p_y), qq and rr belong to ℝ2\mathbb R^2.✦ For three planar points, the orientation determinant is orient⁡(p,q,r)=det⁡(q−p,r−p)=(qx−px)(ry−py)−(qy−py)(rx−px).\operatorname{orient}(p,q,r) =\det(q-p,r-p) =(q_x-p_x)(r_y-p_y)-(q_y-p_y)(r_x-p_x).(1)✦ A finite configuration P=(pi)i∈VP=(p_i)_{i\in V}, indexed by a finite set VV, is in general position if its points are distinct and the determinant in (1) is nonzero for every three distinct indices. A finite configuration P=(pi)i∈VP=(p_i)_{i\in V} has distinct first coordinates if (pi)x≠(pj)x(p_i)_x\ne(p_j)_x whenever i≠ji\ne j.

A straight-line drawing D=(W,E)D=(W,E) on PP consists of a finite vertex set W⊆VW\subseteq V and a finite edge set E⊆W×WE\subseteq W\times W, with each edge (i,j)(i,j) directed from left to right: (pi)x<(pj)x((i,j)∈E).(p_i)_x<(p_j)_x \qquad ((i,j)\in E).(2)✦ Each edge in (2) is drawn as the segment joining its endpoint points. Let F⊆WF\subseteq W be a designated vertex cover of DD.

The open segment of an edge (i,j)(i,j) is the set sij={(1−t)pi+tpj:0<t<1}.s_{ij}=\{(1-t)p_i+tp_j:0<t<1\}.(3) Two edges cross if their open segments from (3) intersect.✦ A crossing pair of DD is an unordered pair of distinct edges that cross, and cr⁡(D)\operatorname{cr}(D) is the number of these pairs.✦ Write v=|W|v=|W| for the vertex count, e=|E|e=|E| for the edge count, and m=|F|m=|F| for the size of the designated cover.

The Claim

Theorem 1. Let PP be a finite configuration in general position with distinct first coordinates. Let D=(W,E)D=(W,E) be a straight-line drawing on PP, and let F⊆WF\subseteq W be a vertex cover of DD. The designated-endpoint crossing bound (4) holds: e3≤2304mvcr⁡(D)+13824v3.e^3\le 2304\,m v\,\operatorname{cr}(D)+13824\,v^3.(4)✦ If e≥24ve\ge24v, the dense bound (5) holds: e3≤2304mvcr⁡(D).e^3\le2304\,m v\,\operatorname{cr}(D).(5)✦

In the paper, the result reads: for a simple graph with a straight-line drawing DD on vv distinct points, with no vertex in an edge interior and no crossings of incident edges, if every edge has an endpoint in a specified set of at most m≤vm\le v vertices, then e3≤2304mvcr⁡(D)+13824v3e^3\le2304\,m v\,\operatorname{cr}(D)+13824\,v^3, where ee is the edge count and cr⁡(D)\operatorname{cr}(D) counts properly crossing edge pairs, and if e≥24ve\ge24v, then e3≤2304mvcr⁡(D)e^3\le2304\,m v\,\operatorname{cr}(D).

What Is Checked

The bounds are stated over finite straight-line drawings satisfying (2), on configurations in general position with distinct first coordinates, with a designated vertex cover and crossings defined by intersection of open edge segments.