51 problems

Let $K_{a,b}$ be the complete bipartite graph with parts of sizes $a$ and $b$, and let $\operatorname{cr}(K_{a,b})$ denote its crossing number. Zarankiewicz's conjecture. … This is…

Let $K_n$ be the complete graph on $n$ vertices, and define … Here $\operatorname{cr}(G)$ denotes the minimum number of crossings in a plane drawing of a graph $G$. Harary–Hill con…

Hill's conjecture. The crossing number satisfies

Let $G_1$ and $G_2$ be graphs embedded on a closed surface $S$, and let the joint crossing number be the minimum number of crossing points between $h(G_1)$ and $G_2$ over all homeo…

Guy–Hill conjecture. The crossing number of $J_n$ is equal to $H'(n)$. The source attributes this conjecture to Guy and Hill; no resolution is stated in the supplied text, so it re…

Convex drawing conjecture. Every graph has a convex rectilinear drawing that maximizes its rectilinear crossing number.

Let $C_{3g}(p_i)$ denote recursively defined clustervertices on three partitions of sizes $p_1$, $p_2$, and $p_3$, where … Translate the clustervertices by integers $a_i$ nearest t…

For positive integers $n$ and $m$, let $\b\a\kappa(n,m)$ be the least crossing number among graphs with $n$ vertices and $m$ edges. Erdős–Guy conjecture. Along any sequence of pair…

Let $Q_d$ be the $d$-dimensional hypercube, let $\mathcal{R}_d$ be the recursively defined drawing described above, and let $CR_{\max}(Q_d)$ denote the maximum rectilinear crossing…

Let $P$ be a generic set of $n$ points in the plane. The linear lower-bound conjecture. … The authors identify this as the most important problem for improving the lower bound for…

Karl–Tóth conjecture. The bound $m^{\rm odd}_1(n)\leq 5n-9$ is far from the truth; probably

Let $K_n$ be the complete graph on $n$ vertices, and let ${\rm cr}_g(K_n)$ denote its crossing number when drawn on the closed surface of genus $g$. The previously known lower boun…

Let $K_n^4$ denote the complete balanced $4$-partite graph with $n$ vertices, and let $\operatorname{cr}(G)$ and $\overline{\operatorname{cr}}(G)$ denote respectively its ordinary…

Let $K_n^3$ denote the complete balanced tripartite graph with $n$ vertices, and let $\operatorname{cr}(G)$ and $\overline{\operatorname{cr}}(G)$ denote respectively the ordinary a…

Nonattainment conjecture. There exists no $f\in\mathcal F$ such that

Let $D$ be the complete geometric graph on $n$ points selected uniformly at random from the unit square. For an interval $I\subseteq \mathbb{R}$, color an edge blue when its slope…

Let $m\ge n$, and let $K_{m,n}^{\mathbf{FIC}}$ be an arrangement in which $m$ vertices of $K_{m,n}$ are randomly distributed inside a circle and the other $n$ vertices lie on its c…

Let $P(4h+2,2h)$ be the generalized Petersen graph with parameters $4h+2$ and $2h$, where $h\geq 3$. Lin et al.'s conjecture. … This conjecture proposes the exact crossing number f…

Lamm's conjecture. $c_t(K)=c(K)$ if and only if $K$ can be represented by a continued fraction expansion $[a_1,\ldots,a_n]$ of type (A) or type (B).

Crossing-number conjectures. Crossing numbers should be additive under connected sums,

Let $M_{n,t}$ be the graph considered in the construction above, and write $k=\lfloor n/2\rfloor$. If a set $P'\subseteq P$ has strength $0$ and $t=|P\setminus P'|$, then the const…

Let $G$ be a graph, and for a surface $[200~\Sigma$ let $\mathop{\rm iocr}\nolimits_{\Sigma}(G)$ denote the fewest number of pairs of independent edges that cross oddly in a drawin…

Let $cr(K_{n,n})$ be the crossing number of the complete bipartite graph $K_{n,n}$, and let $cr_0(K_{n,n})$ be its geodesic crossing number. Define … and … The limits exist, and sa…

Polynomial-degree upper bound conjecture. The quantity $\log f(n,k)$ can be bounded from above by a polynomial in $k$ whose degree does not depend on $n$.

Anshu et al.'s conjecture. Among all $d$-dimensional rectilinear drawings of $K_n^d$, the number of crossing pairs of hyperedges is maximized when all vertices are placed on the…