45 problems

A greedy drawing of a graph $G$ is a Euclidean drawing in which, for every pair of distinct vertices $s,t$, the vertex $s$ has a neighbor $u$ satisfying $d(s,t)>d(u,t)$, where $d$…

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…

Bounded distance-number conjecture. The distance number of every graph with treewidth at most $k$ and degree at most $\ell$ is bounded by

Let $P$ be a finite set of points in the plane in general position, meaning that no three points of $P$ are collinear. Jamison's conjecture. The point set $P$ has a spanning path w…

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…

Let $G$ be a finite planar graph. An integral drawing of $G$ is a plane straight-line drawing $\varphi:V(G)\to\mathbb Z^2$ such that … for every edge $uv\in E(G)$. Harborth's conje…

Consider a length-regular drawing of the $d$-dimensional hypercube, with edge lengths $\ell_1\leq \ell_2\leq\cdots$. Length-profile conjectures. The following assertions are propos…

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 $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…

Clustered fan-crossing conjecture. There exist small integers $k,\ell$ such that every fan-crossing drawing is a $k$-fold $\ell$-clustered fan-crossing drawing, at least in the sub…

Let $K_n$ be the complete graph, let $\mathcal{D}$ be a simple drawing of it on $n\ge 2$ vertices, and let $v$ and $w$ be distinct vertices of $\mathcal{D}$. A crossing-free Hamilt…

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 $g$ be a positive integer, and let $N_g$ be the non-orientable surface of genus $g$. A loopless pseudo-triangulation of $N_g$ is a cellularly embedded loopless multigraph in wh…

Let $G$ be a simple graph. A perfect cross-cap drawing of $G$ is a drawing with $g(G)$ cross-caps in which every edge intersects each cross-cap at most once, where $g(G)$ is the no…

Let $G$ be a loopless graph with a fixed embedding scheme. A perfect cross-cap drawing is a cross-cap drawing with $g(G)$ cross-caps in which every edge intersects each cross-cap a…

Let $Cr_{deg}(G)$ denote the degenerate crossing number of a graph $G$, and let $g(G)$ denote its non-orientable genus. Mohar's equality conjecture. For every graph $G$,…

The uncrossed number of a graph is the minimum number of planar drawings in an uncrossed collection whose union contains every edge of the graph. Here, $NP$ denotes nondeterministi…

Given a graph $G$, let its obstacle number be the minimum number of faces in a straight-line drawing whose union intersects every non-edge, and let $f(h,n)$ denote the number of…

Let $G$ be an augmented caterpillar drawn as a great-circle thrackle, and let $v$ and $v'$ be adjacent vertices in the spine of $G$. A separating $2$-path at a vertex is a $2$-path…

A great-circle thrackleable tree is a tree admitting a thrackle drawing on the sphere in which the edges are great-circle arcs. An augmented caterpillar is the graph class defined…

A thrackle drawing is a drawing of a graph in which every pair of edges meets exactly once; a great-circle thrackle drawing is such a drawing on the sphere using great-circle arcs.…

Pach et al.'s conjecture. For every $k$, there is a max-saturated $k$-planar graph with a simple $k$-planar drawing.

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 $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…

Superlinear area conjecture. There exists a constant $\varepsilon>0$ such that every $n$-node complete ternary tree requires