Visibility Graphs of Points, Segments and Polygons — Problem 36

Definitions and mathematical statement

Let $P$ be a simple polygon, and let $V(P)$ be its finite set of vertices. Under the usual closed-region visibility convention, distinct vertices $u,v\in V(P)$ are visible to each other if the segment $[u,v]$ is contained in the closed polygonal region bounded by $P$. Its visibility graph is the finite simple undirected graph $G=(V,E)$, where $V=V(P)$ and $\{u,v\}\in E$ exactly when $u$ and $v$ are visible. Let $C$ be the Hamiltonian cycle in $G$ whose cyclic vertex order follows the boundary of $P$.

Under the graph-theoretic interpretation of a hidden set, a set $H\subseteq V$ is hidden if its distinct vertices are pairwise nonadjacent: \[ \forall u,v\in H,\qquad u\ne v\Longrightarrow \{u,v\}\notin E. \] Thus a maximum hidden set is a set $H_{\max}\subseteq V$ satisfying \[ H_{\max}\text{ is hidden},\qquad |H_{\max}|=\max\left\{|H|:H\subseteq V\text{ is hidden}\right\}. \] Problem. Given $G$, promised to be the visibility graph of a simple polygon $P$, together with its specified boundary Hamiltonian cycle $C$, determine a maximum hidden set $H_{\max}$ using the supplied graph and cycle.

Unresolved source qualifications. The supplied statement does not define "hidden set" or specify the treatment of boundary contacts in visibility. The formulation above explicitly uses the vertex independent-set interpretation and the closed-region visibility convention; these interpretations require confirmation against the complete source discussion. No coordinates of $P$ are stated to be supplied. The excerpt specifies no running-time requirement, so no polynomial-time requirement is asserted here.

Short English statement

Given a polygon visibility graph and the cycle recording its boundary order, find a largest set of mutually nonvisible vertices. This interprets a hidden set as an independent set of the given graph. The source excerpt leaves the terminology, geometric visibility convention, and intended computational efficiency unspecified.

Sources

• Local UnsolvedMath registry, permanent ID $800562$, source problem code catalogue entry, titled "Visibility Graphs of Points, Segments and Polygons --- Problem 36." The supplied record attributes the problem to Ghosh and Goswami and records the year as 2010.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 36. Supplied source URL: https://arxiv.org/abs/1012.5187. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance claims, not independently verified access or source verification.
• The local record labels the problem open and records an update timestamp of 2026-10-16T14:00:00Z. This is supplied registry status, not an independently verified assessment of the literature.