Linear Bounds for Monotone Crossing Numbers

Definitions and mathematical statement

For a finite simple undirected graph $G$, a conventional plane drawing assigns distinct points to vertices and simple arcs to edges, with each edge joining its endpoints and with no vertex in an edge interior. Crossings are intersections of edge interiors; drawings are taken in general position, so crossings are transverse, finite in number, and involve exactly two edges. The crossing number $\operatorname{cr}(G)$ is the minimum number of crossings over such drawings.

A drawing is $x$-monotone if each edge arc meets each vertical line in at most one point. Under the conventional interpretation, the monotone crossing number $\operatorname{mon\text{-}cr}(G)$ is the minimum number of crossings over $x$-monotone drawings, allowing the vertex positions and their horizontal order to vary. These are working definitions: the supplied record does not specify the drawing conventions, whether graphs must be finite and simple, or whether any vertex order is prescribed.

Let $\mathcal G$ denote the graph class intended by the source. The question, retaining the supplied strict inequality, is whether \[ \exists c\in{\mathbb{R}}\quad\forall G\in\mathcal G,\qquad \operatorname{mon\text{-}cr}(G)<c\,\operatorname{cr}(G). \] Here $c$ must be independent of $G$; a positive constant is the natural intended interpretation, although positivity is not stated explicitly.

There is an unresolved boundary-condition defect in this formulation. If $\mathcal G$ contains a graph with $\operatorname{cr}(G)=0$, the displayed inequality requires a nonnegative crossing number to be strictly less than zero. In particular, the unrestricted phrase "every graph" includes an edgeless graph. A non-strict comparison for all graphs, or a strict comparison restricted to graphs of positive crossing number, would avoid this defect, but the supplied record does not authorize either correction. The intended universal linear-comparison question therefore requires clarification before this can be treated as a definitive mathematical statement.

Short English statement

The supplied question asks whether the monotone crossing number is bounded by a universal constant times the ordinary crossing number. Its strict inequality is incompatible with including graphs of crossing number zero. The intended graph class and drawing conventions also need confirmation. The supplied open status concerns the intended linear-comparison problem and is not independently verified here.

Sources

• Local UnsolvedMath registry, data/unsolvedmath/problems.json, permanent ID $30001897$, title "Linear Bounds for Monotone Crossing Numbers," exact source problem code catalogue entry. The record belongs to the Oberwolfach Reports Open Problems collection, gives proposed year 2011, and names no proposer.
• Supplied source citation: Discrete Geometry (2012), Oberwolfach Reports, DOI 10.4171/owr/2011/44, pp. 2459--2548. https://doi.org/10.4171/owr/2011/44. This is also the supplied literature-source link labelled "OWR 44 (2012)."
• Supplied literature-source link labelled "crossing-number survey": https://www.combinatorics.org/files/Surveys/ds21/ds21v5-2020.pdf.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that the report provides only a quadratic upper bound in the classical crossing number, while the existence of a universal linear comparison remains open. This is supplied dated curation, not an independently verified literature assessment. The background expressly requests independent verification of time-sensitive status and cited claims.
• The supplied statement status is corrected_verified; its accompanying explanation says only that TeX notation was enclosed in math delimiters without changing mathematical content. It does not establish verification of the definitions, boundary conditions, or mathematical formulation.