Suppose a geometric graph has no pairwise k-crossing lines

Definitions and mathematical statement

Fix an integer $k\ge3$. A geometric graph consists of a finite set $V\subset\mathbb R^2$ of $n$ distinct points in general position (no three collinear) and straight segments joining selected pairs. It is simple: there are no loops or repeated edges. Two edges cross when their relative interiors intersect; a shared endpoint is not a crossing. Call the drawing $k$-quasiplanar if it has no $k$ distinct edges every two of which cross.

Is there a constant $C_k$, depending only on $k$, such that every such drawing satisfies \[ |E|\le C_k n\,? \] Equivalently, if $q_k(n)$ is the largest possible number of edges over all eligible point sets and drawings, is $q_k(n)=O_k(n)$? The constant must be independent of both $n$ and the geometry of the chosen vertices.

The forbidden configuration is a clique in the crossing graph of the segments. Many crossings in total, or an edge crossing many other edges, remain permissible when they do not create this clique. No bound is assumed on the number of crossings of the whole drawing. This entry uses the straight-segment convention stated in Cooper's question; extensions allowing curved edges require their own drawing hypotheses. Cases established for particular fixed $k$ do not answer the assertion uniformly over all fixed values of $k$.

Short English statement

For every fixed k, must a geometric graph with no k pairwise crossing edges have only linearly many edges?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100004 (AMR-030-0004), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Geometry, source-order bullet 4. Original source indexed by AMR-030-0004. https://people.math.sc.edu/cooper/combprob.html.