Bounded Pairwise Crossings in Hypercube Drawings

Definitions and mathematical statement

For each integer $d\geq 1$, the hypercube graph $Q_d$ has vertex set $\{0,1\}^d$; two distinct vertices are adjacent exactly when their coordinates differ in exactly one position.

For purposes of this draft, a topological drawing in ${\mathbb{R}}^2$ represents vertices by distinct points and edges by simple arcs joining their endpoint points. The interior of an edge arc contains no vertex point. Intersections between distinct edge interiors are finitely many proper crossings. Two distinct edges cross if their interiors have at least one proper crossing; sharing a vertex alone does not count. A collection of edges is pairwise crossing if every two distinct edges in the collection cross. These drawing conventions are provisional: the supplied record does not specify whether further restrictions, such as forbidding crossings between adjacent edges or allowing at most one intersection between any two edges, are intended. Such restrictions are not imposed here and require verification against the report.

Question. Does there exist an integer $c\geq 1$, independent of $d$, such that for every integer $d\geq 1$ there is a topological drawing $D_d$ of $Q_d$ in ${\mathbb{R}}^2$ with no set of $c$ distinct pairwise crossing edges? Equivalently, does \[ \exists c\in{\mathbb{Z}}_{\geq 1}\;\forall d\in{\mathbb{Z}}_{\geq 1}\;\exists D_d\;\forall F\subseteq E(Q_d),\qquad |F|=c\ \Longrightarrow\ \exists e,f\in F\;\left(e\neq f\ \text{and }e,f\text{ do not cross in }D_d\right) \] hold, where $D_d$ ranges over the intended class of topological drawings? If the source includes $0$ in ${\mathbb{N}}$, the additional graph $Q_0$ is a single vertex with no edges and does not change the question.

The supplied report excerpt relates this question to whether, for each fixed $k$, the maximum number of edges of an $n$-vertex $k$-quasi-planar graph is bounded linearly in $n$. Here $k$-quasi-planarity means admitting a drawing with no $k$ pairwise crossing edges, subject to the intended drawing conventions. This is supplied context, not an asserted equivalence or a second target problem.

Short English statement

Can every hypercube be drawn in the plane so that the size of any collection of pairwise crossing edges is bounded by one constant independent of the dimension? The exact permitted drawing conventions need source verification. The supplied registry labels the question open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry, supplied complete record: permanent ID $30005814$, source problem code catalogue entry, title "Bounded Pairwise Crossings in Hypercube Drawings." The supplied record belongs to the Oberwolfach Reports Open Problems collection and gives proposed year 2024; no individual proposer is identified. Its statement status is corrected_verified, with the supplied assertion that the statement was reconstructed and checked against the official report. That assertion has not been independently verified here.
• Discrete Geometry (2024), Oberwolfach Reports, pp. 137--202, DOI 10.4171/owr/2024/3. Supplied report citation and literature source: https://doi.org/10.4171/owr/2024/3. The supplied excerpt labels the hypercube question "Question 1."
• The Number of Edges in k-Quasi-planar Graphs. Supplied literature source: https://doi.org/10.1137/110858586.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the question open in the report's formulation and states that known $k$-quasi-planar results provide edge bounds under drawing restrictions but do not provide an absolute crossing-clique bound for all hypercubes. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment. Time-sensitive status and the cited claims require independent verification.