Visibility Graphs of Points, Segments and Polygons — Problem 23

Definitions and mathematical statement

The supplied record contains two questions. Its definition of a bar $k$-visibility graph, its graph-domain conventions, and some of its quantifiers are not supplied, so the formulations below remain conditional on those conventions.

A candidate standard interpretation is the following. For an integer $k\geq 0$, represent the vertices of a finite simple undirected graph by pairwise disjoint nondegenerate horizontal line segments, called bars, in ${\mathbb{R}}^2$. Two distinct vertices are adjacent if and only if a vertical strip of positive width connecting their bars intersects at most $k$ other bars between them. Write $\mathcal B_k$ for the class admitting such a representation. This interpretation, including positive-width visibility and the requirement that every visible pair be an edge, requires confirmation from the cited source; the supplied record itself gives no definition.

A graph is triangle-free if it contains no cycle of length three. It is planar if it admits a drawing in the plane with no crossings between edge interiors. For finite simple graphs $H$ and $G$, write $H\preccurlyeq G$ if $H$ is isomorphic to a subgraph of $G$, without requiring that subgraph to be induced. Under this literal meaning of forbidden subgraph, define \[ \mathcal F_k=\{H: \text{for every }G\in\mathcal B_k,\ H\not\preccurlyeq G\}, \qquad \mathcal T=\{H:H\text{ is triangle-free and non-planar}\}. \] The record supplies the assertion that triangle-free non-planar graphs are forbidden subgraphs of bar $k$-visibility graphs. On the preceding interpretation, this would assert $\mathcal T\subseteq\mathcal F_k$. The range and quantification of $k$ in this assertion are unspecified, and the assertion is recorded here as a source claim rather than an independently verified theorem.

The first question asks whether there is any other class of forbidden subgraphs. For a fixed $k$ in the intended, unspecified range, a literal formulation is to identify a class $\mathcal C_k$ satisfying \[ \mathcal C_k\subseteq\mathcal F_k, \qquad \mathcal C_k\setminus\mathcal T\ne\varnothing. \] It remains unresolved whether the source means ordinary forbidden subgraphs, forbidden induced subgraphs, or graphs excluded from membership in $\mathcal B_k$. These interpretations give different questions; the displayed formulation uses ordinary subgraphs only conditionally.

A graph is $r$-regular if every vertex has exactly $r$ neighbors. The second question is whether there exist $(2k+2)$-regular bar $k$-visibility graphs for $k\geq 5$. Under a finite, nonempty, simple-graph interpretation and a universal reading of the parameter, this asks whether \[ \forall k\in{\mathbb{Z}}_{\geq 5}\quad \exists G\in\mathcal B_k\quad \left(|V(G)|>0\ \text{ and }\ \forall v\in V(G),\ \deg_G(v)=2k+2\right). \] The source does not explicitly say whether existence is required for every such $k$, for some such $k$, or for another subset of these parameters. The universal reading displayed above, and the finite nonempty graph convention, require confirmation.

Short English statement

The record asks for further forbidden classes for bar $k$-visibility graphs and asks whether $(2k+2)$-regular examples exist for $k\geq 5$. The visibility convention, the meaning of forbidden subgraph, and the parameter quantifiers need confirmation. The supplied open status and the claimed exclusion of triangle-free non-planar graphs are source labels and assertions, not independently verified conclusions.

Sources

• Local UnsolvedMath registry, permanent ID $800550$, exact source problem code catalogue entry, title: Visibility Graphs of Points, Segments and Polygons --- Problem 23. The supplied registry attributes the problem to Ghosh and Goswami, with proposed year $2010$, and labels its status as open.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 23. Supplied source URL: https://arxiv.org/abs/1012.5187. The provenance records access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance statements, not a claim of independent source access or verification.
• The supplied registry record was created and updated on 2026-10-16T14:00:00Z, with upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. Both questions are retained from this record; their placement together under Problem 23 has not been independently checked.