22 problems

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…

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…

Maximizer structure conjecture. The following properties hold:

Hill's conjecture. The crossing number satisfies

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 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 $d\geq 3$, and let $p:[n]\to{\mathbb R}^d$ satisfy $\|p(i)\|=1$ for every $i\in[n]$ and … Assume that the image of $p$ has size at least $3$. Second-largest eigenvalue conjectu…

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…

Spider lower-bound conjecture.

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…

Let $G=(B,U,E)$ be a geodesic net in the plane, with balanced vertices $B$ and unbalanced vertices $U$. For a vertex $v$, let $\operatorname{imb}(v)$ denote the norm of the sum of…

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…

A tangent graph of a finite collection of circles in the plane has one vertex for each circle and an edge when two circles are tangent. Assume that no more than two circles pass th…

A tangent graph has one vertex for each disc and an edge when the corresponding discs are tangent. Pinchasi–Sharir tangent-incidence conjecture. (i) Planar tangent graphs with $n$…

Let $G$ be a geometric graph embedded in $\mathbb R^d$, with edges joining pairs at the diameter distance. Call $G$ stress-free if there are no not-all-zero edge weights whose weig…

Let $K\subseteq\mathbb R^d$ be a set of points, let $D$ be the set of pairs of points in $K$ at the diameter distance, and call $(K,D)$ general if every continuous deformation of t…

Linear edge bound conjecture. A graph $G$ on $n$ vertices belonging to the class $R_2$ can have at most $O(n)$ edges.

3-symmetric optimal-drawing conjecture. For each positive integer $n$ divisible by $3$, there is an optimal geometric drawing of $K_n$ that is 3-symmetric.

3-decomposability conjecture. For each positive integer $n$ divisible by $3$, all optimal rectilinear drawings of $K_n$ are 3-decomposable.