Visibility Graphs of Points, Segments and Polygons — Problem 34

Definitions and mathematical statement

Let $P\subset{\mathbb{R}}^2$ be a simple polygon, regarded as its boundary together with its enclosed region, with $n\geq3$ distinctly labelled vertices. Under the closed-polygon visibility convention, its vertex visibility graph $\operatorname{Vis}(P)$ is the undirected simple graph whose vertices are the vertices of $P$, with distinct vertices $u,v$ adjacent exactly when the segment $[u,v]$ is contained in $P$. This convention includes polygon boundary edges. The supplied record does not explicitly specify the visibility convention or impose general-position assumptions; the definition here is therefore a convention requiring source confirmation.

A Hamiltonian cycle in a graph is a cycle visiting every vertex exactly once before returning to its starting vertex. Cyclic orderings representing such a cycle are identified up to rotation and reversal. Write $C_P$ for the Hamiltonian cycle formed by the boundary edges of $P$.

Source request. Given only a graph $G$, promised to be the vertex visibility graph of an unspecified simple polygon $P$, determine the Hamiltonian cycle $C_P$ corresponding to the boundary of $P$. The polygon coordinates and its boundary ordering are not supplied as input. As the source emphasizes, $G$ may have several Hamiltonian cycles, and a Hamiltonian cycle in $G$ need not be realizable as the boundary of a polygon having visibility graph $G$.

Unresolved output qualification. The record does not distinguish recovering the boundary ordering of the particular hidden polygon $P$ from finding any compatible boundary ordering. The latter has the precise search formulation: for every promised input graph $G$ on a labelled vertex set $V$, output a Hamiltonian cycle $C$ in $G$ such that there exists a simple polygon $Q$ with vertices labelled by $V$ satisfying \[ \operatorname{Vis}(Q)=G,\qquad C_Q=C. \] Here equality respects the vertex labels. Recovering the boundary of the particular hidden polygon would instead require $C=C_P$. The supplied record does not establish that this stronger target is determined by $G$. These targets must not be silently identified. No running-time requirement is stated in the supplied record.

Short English statement

Given a graph known to be the vertex visibility graph of a simple polygon, determine a Hamiltonian cycle representing the polygon boundary. The source leaves unresolved whether any realizable boundary cycle suffices or whether the boundary of the particular hidden polygon must be recovered. The visibility convention and intended algorithmic requirement also need confirmation.

Sources

• Local UnsolvedMath registry: permanent ID $800560$, exact source problem code catalogue entry; title: Visibility Graphs of Points, Segments and Polygons --- Problem 34. The supplied registry attributes the problem to Ghosh and Goswami, with proposed year 2010, and labels it open. This is a supplied status label, not an independently verified mathematical or literature assessment.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 34. Supplied source URL: https://arxiv.org/abs/1012.5187. The source record reports access on 2026-10-16 and extraction by arxiv_latex; these provenance claims are supplied and have not been independently verified here.