25 problems

In a graph drawing, a simple drawing is one in which both adjacent edges and non-adjacent edges satisfy the relevant simplicity conditions; a plane Hamiltonian cycle is a cycle tha…

Minimum empty-triangle conjecture. Every simple drawing of $K_n$ has at least

Product-structure conjecture for $k$-independent crossing graphs. The class of $k$-independent crossing graphs admits product structure.

The no-product-structure conjecture. For every $\alpha < s(n)$, the class of intersection graphs of $\alpha$-free homothetic regular $n$-gons does not have product structure.

The canonical-drawing characterization. The class of intersection graphs of $\alpha$-free homothetic regular $n$-gons admits product structure if and only if their canonical drawin…

Uncrossed-number separation conjecture. The uncrossed number can be arbitrarily far apart from the outerthickness. This conjecture asks whether the difference between these two gra…

A plane integral drawing of a graph is a drawing in the plane in which edges are represented by straight-line segments of integer length and no two edges cross except possibly at a…

KPTU's conjecture. Every separated single-crossing, but not necessarily locally star-like, drawing on $n$ vertices has

Rectangular-flat-torus grid contact conjecture. Every bipartite toroidal graph without loops has a grid contact representation on the rectangular flat torus.

Rectangular-flat-torus tessellation conjecture. Every toroidal graph without loops has a tessellation representation on the rectangular flat torus.

Pach et al.'s conjecture. For all $k,n\geq 1$, this maximum is attained by a graph that admits a simple $k$-plane drawing.

Obstruction-list conjecture. There is a list-of-obstructions characterization of exactly when a drawing of $G$ has such an extension.

Potential crossing pair conjecture. The graph $G$ has crossing number at least $2$ if and only if it does not have a potential crossing pair.

Pach et al.'s conjecture. Every $n$-vertex $k$-quasi-planar graph has at most

A simple complete topological graph is a drawing of a complete graph in the plane in which any two edges meet at most once, either at a common endpoint or at a proper crossing. A r…

Let $G$ be a planar graph, and let $\operatorname{obs}(G)$ denote its obstacle number. Planar obstacle-number conjecture. If $G$ is a planar graph, then … The paper had not found a…

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…

Crossing-number equality conjecture.

Rectilinear crossing-number conjecture.

Let $D$ be a simple drawing of a graph, and let $E_{{\le}{\le}{\le}k}(D)$ denote the number of its $\le\!\le\!\le k$-edges, with … Here $E_i(D)$ denotes the number of $i$-edges in…

Let $D$ be a simple drawing of a graph, and let $E_{{\le}{\le}{\le}k}(D)$ denote the number of its $\le\!\le\!\le k$-edges, defined by … Here $E_i(D)$ denotes the number of $i$-edg…

For a graph $G$, let $\operatorname{cr}(G)$ be its crossing number, the minimum number of crossings in a drawing of $G$, and let $\operatorname{pcr}(G)$ be its pair-crossing number…

A simple drawing is extendible if its edges are contained in a pseudoline arrangement: each edge lies on a simple unbounded curve, and any two such curves intersect at most once. A…

A drawing of a graph represents vertices by distinct plane points and edges by simple curves, with a vertex meeting an edge only at an endpoint. A drawing is simple if any two edge…

Let $K_n$ be the complete graph on $n$ vertices, and let ${\textup{\textsf{dn}}_{}(G)}$ denote the distance-number of a graph $G$. Distance-number conjecture for complete graphs. ……