22 problems

Polynomial-size grid drawing problem. For every planar graph $G$, there is a proper grid drawing of $G$ in a grid of polynomial size.

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 $\theta_o(G)$ denote the outerthickness of a graph $G$, and let $\operatorname{unc}(G)$ denote its uncrossed number. Unbounded-gap conjecture. For every positive integer $k$, t…

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 $K_n$ be the complete graph, and let a simple drawing be a drawing in which any two edges have at most one common point and no two edges incident to the same vertex cross. A cr…

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…

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…

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

For a graph, book thickness is the minimum number of pages in a book embedding, and convex antithickness is the minimum number of convex geometric thrackles in a straight-line draw…

For a graph, geometric thickness is the minimum number of plane geometric layers in a straight-line drawing, and geometric antithickness is the minimum number of geometric thrackle…

Subdivision conjecture. Every graph has a subdivision obtained by multiplying subdividing its edges such that the resulting graph belongs to $\mathcal{G}_s^s$.

2-degeneracy conjecture. If $G\in\mathcal{G}_s^s$, then $G$ is $2$-degenerate; that is, every non-empty induced subgraph of $G$ has a vertex of degree at most $2$.

A graph is IC-planar if it has a plane drawing in which no two crossings share an endpoint, and NIC-planar if it has a plane drawing in which any two crossings share at most one en…

Bar 1-visibility conjecture. Every 1-planar graph is a bar 1-visible graph.

A good set of slopes is a set with which every cubic graph has a straight-line drawing. Finite graph characterization conjecture. There is a not necessarily connected finite graph…

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

Convex-polygon realization conjecture. The maximum rectilinear crossing number of $G$ can be realized in a convex-polygon drawing.