Visibility Graphs of Points, Segments and Polygons — Conjecture 16

Definitions and mathematical statement

For a finite simple graph $G=(V,E)$, a Hamiltonian cycle is a cyclic ordering $v_1,\ldots,v_n$ of all vertices, where $n=|V|\geq 3$, the vertices are distinct, and $\{v_i,v_{i+1}\}\in E$ for every $i$, with $v_{n+1}=v_1$.

The supplied Conjecture 16 asserts that every segment visibility graph $G$ has a Hamiltonian cycle $C$ whose realization in the associated embedded segment visibility graph $G'$ is the boundary of a circumscribing polygon.

More explicitly, if $G'$ realizes each vertex $v$ at a distinct point $p(v)\in{\mathbb{R}}^2$ and each edge as the straight segment joining its endpoints, the requested cycle must admit an ordering as above such that the polygonal chain \[ p(v_1),p(v_2),\ldots,p(v_n),p(v_1) \] is a simple closed polygonal curve and bounds a polygon $P$ satisfying \[ \partial P=\bigcup_{i=1}^{n}[p(v_i),p(v_{i+1})]. \] The polygon $P$ must additionally circumscribe the underlying segment configuration in the sense intended by the source.

The supplied record does not define the admissible segment configurations, the visibility relation, the construction of $G'$, or the meaning of a circumscribing polygon. Accordingly, the straight-line description above explains the boundary requirement conditionally; it does not supply the missing source conventions. In particular, no assumptions of disjointness, general position, or a minimum configuration size, and no containment or boundary-incidence requirements for the input segments, are imposed here without source support. The universal quantifier is over the source's intended class of segment visibility graphs, whose precise scope remains unresolved.

Short English statement

The supplied conjecture asks whether every segment visibility graph has a Hamiltonian cycle that traces the boundary of a polygon circumscribing its underlying segment configuration. The admissible configurations and the meanings of visibility and circumscription require clarification from the source. The registry labels the problem open; this draft does not independently verify that status.

Sources

• Local UnsolvedMath registry, permanent ID $800545$, exact source problem code catalogue entry, title "Visibility Graphs of Points, Segments and Polygons --- Conjecture 16." Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Conjecture 16. Supplied source URL: https://arxiv.org/abs/1012.5187. The registry attributes the problem to Ghosh and Goswami and gives proposed year 2010.
• Supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance claims; the source has not been independently visited or verified for this draft. The supplied registry status is open.