Visibility Graphs of Points, Segments and Polygons — Problem 10

Definitions and mathematical statement

Interpret a graph as a finite simple undirected graph. The supplied excerpt does not define obstacle number, so the following polygonal model is explicit but provisional. An obstacle representation of a graph $G=(V,E)$ consists of an injective map $p:V\to{\mathbb{R}}^2$ and a finite collection $\mathcal O$ of pairwise disjoint closed polygonal regions, none containing a point of $p(V)$, such that, for distinct $u,v\in V$, \[ \{u,v\}\in E \quad\Longleftrightarrow\quad [p(u),p(v)]\cap\bigcup_{O\in\mathcal O}O=\varnothing. \] Here $[p(u),p(v)]$ is the closed straight line segment joining the two points; under this convention, touching an obstacle boundary blocks visibility. The obstacle number $\operatorname{obs}(G)$ is the minimum number of obstacles in such a representation, allowing the empty collection. No convexity requirement is imposed in this provisional model. The excerpt does not specify polygonality, disjointness, boundary conventions, general position requirements, or restrictions on obstacle placement; the intended source definition must therefore be checked before adopting this model as definitive.

With the intended obstacle convention fixed, the first question is: for each integer $h\ge 2$, determine \[ n(h)=\min\left\{|V(G)|:G\text{ is a finite simple graph and }\operatorname{obs}(G)=h\right\}. \] This minimum is understood only when the displayed class is nonempty; the supplied excerpt does not provide an existence statement for every $h$.

A graph is planar if it admits a drawing in the plane in which edges intersect only at common endpoints. The second question, literally as supplied, asks whether \[ \forall G\;\left(G\text{ is a finite simple planar graph}\ \Longrightarrow\ \operatorname{obs}(G)=1\right). \] The wording may instead intend the assertion with $\operatorname{obs}(G)\le 1$. These formulations are distinct when zero obstacles are allowed, and the supplied excerpt does not resolve which is intended. The planar drawing is not required to be the straight line visibility representation.

Short English statement

For each integer $h\ge 2$, determine the fewest vertices in a graph whose obstacle number is exactly $h$. The record also asks whether every planar graph has obstacle number $1$. Its obstacle conventions and whether the latter means exactly one or at most one require clarification from the source.

Sources

• Supplied local problem registry: AMR Open Problem Lists, permanent UnsolvedMath ID $800540$, exact source problem code catalogue entry; title: Visibility Graphs of Points, Segments and Polygons --- Problem 10.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 10. Supplied source URL: https://arxiv.org/abs/1012.5187. The registry attributes the problem to Ghosh and Goswami and records proposed year 2010.
• Supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance claims, not an independent verification of the source or its contents.
• The registry labels the record open and records an update on 2026-10-16. This is a supplied status label, not an independently verified assessment of the literature or either question.