34 problems

Hill's conjecture. The crossing number satisfies

Harborth's conjecture. The maximum number of edges of a matchstick graph on $n$ vertices is

Bollobás–Meir conjecture. For any finite set of points $X\subseteq[0,1]^k$, there exists a Hamiltonian cycle $H$ on $X$ with $S_k(H)\leq 2\cdot k^{k/2}$ if $k\neq3$, and…

Let $\chi_{\varepsilon}(\mathbb{R}^2)$ denote the least number of colors in a coloring of the plane with no monochromatic pair of points at a distance in…

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

Let $G$ be a 4-connected planar triangulation. A contact representation by homothetic triangles represents the vertices of $G$ by homothetic triangles whose prescribed contacts cor…

Let $K_{3(q-1)+1}$ be the complete graph on $3(q-1)+1$ vertices, and consider any drawing of this graph in the plane. For a triangle of edges and a point not on it, its winding num…

Let $n\geq 2$ be a positive integer, and let $\mathcal{F}$ be the class of intersection graphs of families of spheres in $\mathbb{R}^n$. The asymptotic dimension of a graph class i…

Maximizer structure conjecture. The following properties hold:

Quadratic-asymptotics conjecture. The function $m(n)$ has quadratic asymptotics in $n$.

For a rectilinear drawing of the complete graph $K_n$, let $e_k(K_n)$ denote the number of edges crossed exactly $k$ times, and let … denote the maximum of $e_k(K_n)$ over all rect…

Uniqueness conjecture for the $K_{3,3}$ embedding. The proposed embedding of $K_{3,3}$, with coordinates as described in the table, is unique up to an isometry.

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 $G=(V,E)$ be a graph with $n=|V|$ vertices. A RAC$_2$ graph is a graph admitting a drawing in which edges are polylines with two bends and every pair of crossing edges meets at…

Let $d$ be a positive integer. Let $X$ be an even set of distinct points in $\mathbb R^d$ with minimum distance $r>0$, and let $\mathcal M$ be a max-sum matching of $X$. The closed…

Let $p:[n]\to{\mathbb R}^d$ be injective. Large-eigenvalue sum conjecture. The sum of the $n$ largest eigenvalues of $L(K_n,p)$ is at least … The conjecture improves the previously…

Let $f(k)$ be the maximum number of extremal edges of a convex-packable plane path with $k$ edges. The source establishes the upper bound $f(k)\leq 2\sqrt{k}$ for every positive in…

Let $\mathcal{P}(G)$ denote the set of plane drawings of a graph $G$, and let $\Theta_2$, $\Theta_3$, and $\Theta_4$ be the three plane triangulated cycles shown in the source. A s…

Aichholzer's conjecture. Every such matching $G$ admits a compatible perfect matching.

Spider lower-bound conjecture.

Algorithmic conjecture. The drawing algorithm gives the maximum rectilinear crossing number for every spider $S$.

Let $K_n$ be a complete geometric graph on $n$ points in general position in the plane. A family of subgraphs is $K_3$-intersecting if every two members intersect in a triangle. Qu…

Newborn–Moser conjecture. The maximal number of plane Hamiltonian cycles should be of the form

Let $X_n$ denote the gyroelongated $n$-bipyramid, and let ${\operatorname{{obs}}}_\mathrm{out}(X_n)$ be its outside obstacle number. Obstacle-number conjecture. If $n\geq 4$, then…

Let $4\mathcal{F}={\mathcal{R}_1,\ldots,\mathcal{R}_n}$ be a family of pseudo-disks in the plane whose interiors are pairwise disjoint, and let $\mathcal{H}_{\mathcal{F}}$ be the h…