Visibility Graphs of Points, Segments and Polygons — Problem 9

Definitions and mathematical statement

Let $G=(V(G),E(G))$ be a finite simple undirected graph, and let $|V(G)|$ denote its number of vertices. This graph convention is the intended interpretation of the extremal question; it is not explicitly specified in the supplied excerpt. Write $\operatorname{obs}_{\mathrm{src}}(G)$ for the obstacle number of $G$ under the conventions of the cited source. The supplied record does not define obstacle number or specify admissible obstacles, representations, visibility boundary conventions, or general-position requirements. Thus the formulation below is conditional on recovering that definition from the source; those geometric conventions are not fixed by this draft.

For each integer $h\geq 2$, define \[ \mathcal{G}_h=\{G: G\text{ is a finite simple undirected graph and }\operatorname{obs}_{\mathrm{src}}(G)=h\}. \] Set \[ m(h)= \begin{cases} \min\{|V(G)|:G\in\mathcal{G}_h\},&\mathcal{G}_h\neq\varnothing,\\ +\infty,&\mathcal{G}_h=\varnothing. \end{cases} \] The value $+\infty$ is only a convention making the extremal quantity defined if the relevant class is empty.

Problem. Determine $m(h)$ for every integer $h\geq 2$. The requirement is obstacle number exactly $h$.

The supplied survey excerpt reports that Alpet et al. [akl-ong-2010] and Mukkamala et al. [mps-glon-2010] studied obstacle numbers $1$ and $2$, and attributes to Mukkamala et al. the existence, for every integer $h\geq 3$, of a graph with obstacle number exactly $h$. Under the finite-graph interpretation, this reported existence statement makes $m(h)$ finite for $h\geq 3$. The excerpt does not explicitly supply the corresponding existence statement for $h=2$. It attributes the extremal question to Alpet et al. and describes it as still open. These are supplied source assessments, not independently verified claims.

Short English statement

For each integer $h>1$, determine the fewest vertices needed by a graph whose obstacle number is exactly $h$. The source's definition of obstacle number must be recovered before the geometric formulation is complete. The supplied record labels the problem open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry, permanent ID $800539$, source problem code catalogue entry, title "Visibility Graphs of Points, Segments and Polygons --- Problem 9." The supplied record lists Ghosh and Goswami as proposers, gives the year 2010, and carries the status open. Its creation and update timestamps are both 2026-10-16T14:00:00Z; these are registry metadata, not independent mathematical verification.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 9. Supplied source URL: https://arxiv.org/abs/1012.5187. The provenance records access on 2026-10-16 and extraction by arxiv_latex. This access date is supplied provenance; no source visit or independent verification is asserted here.
• Alpet et al., source reference label [akl-ong-2010]. The supplied excerpt attributes the extremal question and work on obstacle numbers $1$ and $2$ to this reference. The spelling "Alpet" is retained from the record. No full bibliographic entry or separate URL is supplied.
• Mukkamala et al., source reference label [mps-glon-2010]. The supplied excerpt attributes work on obstacle numbers $1$ and $2$, and the existence result for every integer $h\geq 3$, to this reference. No full bibliographic entry or separate URL is supplied.