22 problems

A stable representation is an ${\mathcal{M}}$-representation that is a local minimum with respect to the ordering relation defining stability. Consider a graph on the sphere and fi…

A stable representation of a graph is an ${\mathcal{M}}$-representation that is a local minimum with respect to the ordering relation defining stability. Finite algorithm conjectur…

A graph is representable as a visibility graph if it admits a visibility representation by regions whose unblocked sightlines correspond exactly to the edges of the graph. Connecte…

Let $G$ be a planar graph. For each internal face $F$ in a plane drawing of $G$, let $G_F$ denote the subgraph induced by the vertices incident with $F$. Compact visibility conject…

Let $G$ be a 3-colorable planar graph. A segment representation of $G$ assigns a straight line segment in the plane to each vertex of $G$ so that two segments intersect if and only…

Let $\mathrm{pdd}(n)$ denote the minimum dimension required to realize a dichotomous ordinal complete graph on $n$ vertices, and let $\mathrm{sp}(G)$ be the sphericity of a graph…

Non-word-representability conjecture. For every odd integer $n\ge 3$, the graph $\mu(C_n)$ is not word-representable.

Chordal graph representation conjecture. Let $H$ be a chordal graph. There are chordal graphs $G$ and $G'$ such that $H$ is isomorphic to both $C(G)$ and $C_R(G')$.

A $k$-DIR graph is an intersection graph of line segments in the plane whose segments lie in at most $k$ directions. A planar graph is a graph that can be embedded in the plane wit…

Parikh word representation conjecture. Every bipartite permutation graph with $n$ vertices admits a Parikh word representation over an alphabet of

The no-representation conjecture. The $(n+1)$-cube has no dot product representation in $\mathbb R^n$. This conjecture was disproved by the second author, so the claimed nonexisten…

Babbitt et al.'s conjecture. The complete graph $K_{3k+4}$ is not a semi-arc $k$-visibility graph.

Polynomial-time recognition conjecture for restricted $B_k$-VPG graphs. Applying similar restrictions to the $B_k$-VPG graph class should yield polynomial-time recognition algorith…

Asinowski et al.'s recognition conjecture. For every $k$, recognizing whether a graph is in $B_k$-VPG is NP-complete.

Asinowski et al.'s strict hierarchy conjecture. For every $k>0$,

An EPG representation of a graph represents each vertex by a path in the square grid, with adjacency corresponding to sharing a grid edge; a path has a bend at each change of grid…

An outerplanar graph is a graph that admits a planar embedding in which every vertex lies on the boundary of the outer face. An EPG representation represents each vertex by a grid…

For a graph $G$, the convex obstacle number is the smallest number of convex polygonal obstacles in an obstacle representation of $G$, while the disjoint convex obstacle number is…

Centre conjecture. A suitably defined notion of a “centre” of an optimal representation of every graph must coincide with the centre of the ellipsoid.

Simple-treewidth bend-number conjecture. For $k\geq 3$, the maximal bend-number of graphs satisfying

Bend-number realization conjecture. For every positive integer $k$, there is a graph $G$ such that

The PSI representation bound conjecture. If such a graph has a PSI-representation, then