55 problems

Let $n\ge3$ be odd, and let $G$ be a complete geometric graph on $n$ vertices that can be decomposed into $\left\lceil\frac{n}{2}\right\rceil+1$ plane star-forests. Convex-hull-siz…

Let the dilation of a geometric graph be the maximum, over pairs of vertices, of the ratio between the shortest-path length in the graph and their Euclidean distance. Chew's conjec…

Concentrating-parameter criterion. It is necessary and sufficient for

Let $P$ be a set of $n$ points in the plane in general position. A non-crossing spanning tree on $P$ is a spanning tree with vertex set $P$ whose edges are pairwise non-crossing st…

Let a finite planar point configuration be a finite set of points in the plane, where the closest neighbors of a point are the points minimizing Euclidean distance from it. Karabeg…

Plane spanning tree partition conjecture. Every complete geometric graph on $2n$ vertices can be partitioned into $n$ plane spanning trees.

For $k\geq 2$, let $f(k,n)$ be the maximum number of edges in a geometric graph on $n$ vertices that contains no $k$ pairwise disjoint edges. Bound on disjoint-edge-free geometric…

Let $T$ and $T'$ be non-crossing spanning trees on the same point set, and let $\operatorname{dist}(T,T')$ denote their flip distance. A boundary edge is an edge joining consecutiv…

Let $T$ and $T'$ be non-crossing spanning trees on the same point set, and let $\operatorname{dist}(T,T')$ denote their flip distance. An edge common to $T$ and $T'$ is called a ha…

Let $P$ be a set of $n$ points in convex position. The flip graph $\mathcal{F}(P)$ has one vertex for each non-crossing spanning tree on $P$, with two vertices adjacent when their…

Constraint-induced optimizer conjecture. Among optimizers caused by these constraints, the only possible values of $\alpha$ are

Finite-alpha-values conjecture. Outside the critical window $k=2/(3-\tau)$, every unique optimal $\alpha_i$ belongs to the finite set $\{0,(\tau-2)/(\tau-1),1/2,1/(\tau-1)\}$. The…

Phase-transition conjecture. The phase transition is sharply separated by the curve $k=2/(3-\tau)$. This would extend the corresponding behavior known for clique counts to Hamilton…

Let $k$ be a positive integer, and let $G$ be a complete geometric graph on $2k$ points. A $k$-staircase is the point-set construction defined earlier in the source. Staircase char…

A complete geometric graph is a complete graph drawn with vertices in general position and straight-line edges. A plane star-forest is a forest whose connected components are stars…

A complete geometric graph is a complete graph drawn with vertices in general position and straight-line edges. A plane $k$-star-forest is a star-forest with at most $k$ connected…

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…

Plane spanning-tree decomposition conjecture. Every complete geometric graph on $2m$ vertices can be decomposed into $m$ plane spanning trees.

Plane star-forest covering conjecture. There is no complete geometric graph with $n$ vertices that can be decomposed into fewer than

Let $G$ be a graph. Its separation dimension is the smallest positive integer $d$ for which there is an embedding $\phi:V(G)\to\mathbb{R}^d$ such that, whenever $\\{x,y\\}$ and…

Let $S$ be a point set with $3n$ elements in the plane in general position. An intersecting edge-disjoint triangle family is a family of edge-disjoint triangles such that every two…

Let $S$ be a point set in the plane in general position, and let a longest Hamiltonian cycle be a Hamiltonian cycle on $S$ whose total edge length is maximal. Longest-cycle crossin…

Let $S$ be a set of $n$ points in the plane in general position. An elbow is an orthogonal geometric-graph edge consisting of one horizontal and one vertical line segment, and a cr…

Let $S$ be a set of $n$ points in the plane in general position. An intersecting family of triangles is a family of edge-disjoint triangles whose edges intersect pairwise. Lara and…

Let $S$ be a set of $n$ points in the plane in general position. A crossing matching is a matching whose every pair of edges crosses. Aronov et al.'s conjecture. Every such point s…