Visibility Graphs of Points, Segments and Polygons — Conjecture 14

Definitions and mathematical statement

Let $\mathcal S$ denote the class of graphs intended by the term segment visibility graph in the supplied source. The supplied extract does not define this class: in particular, it does not specify the permitted segment configurations, the vertices, the visibility relation, or the treatment of degeneracies and small configurations. These conventions require confirmation from the source before the statement can be considered fully specified.

For a graph $G=(V,E)$, a Hamiltonian cycle means a cyclic ordering $(v_1,\ldots,v_n,v_1)$, where $n\geq 3$, such that the vertices $v_1,\ldots,v_n$ are distinct, $V=\{v_1,\ldots,v_n\}$, and \[ \{v_i,v_{i+1}\}\in E\quad(1\leq i<n), \qquad \{v_n,v_1\}\in E. \] This graph-theoretic definition imposes no condition that a geometric drawing of the cycle be non-self-intersecting.

The supplied statement of Conjecture 14, attributed to Ghosh and Goswami (2010), is \[ \text{Every }G\in\mathcal S\text{ contains a Hamiltonian cycle.} \] The intended size restrictions on $\mathcal S$, including the treatment of graphs with fewer than three vertices, are not supplied.

The extracted statement also contains a figure caption referring to an unavailable configuration of points $p_1,\ldots,p_{10}$. It describes \[ (p_1,p_{10},p_9,p_8,p_7,p_5,p_4,p_6,p_3,p_2,p_1) \] as Hamiltonian but self-intersecting, and \[ (p_1,p_9,p_{10},p_7,p_8,p_6,p_5,p_4,p_3,p_2,p_1) \] as a Hamiltonian circuit because it forms the boundary of a simple polygon. Thus the caption distinguishes the graph-theoretic cycle condition from the additional geometric requirement of bounding a simple polygon. It further states that the illustrated configuration has no alternating cycle because both endpoints of $p_9p_{10}$ belong to the convex hull of the segments, citing [rit-cscf-90]. The configuration, the definition of an alternating cycle, and the cited reference are not supplied; this caption is retained as source context, not as an independently specified assertion or an additional conclusion of the conjecture.

Short English statement

The supplied conjecture says that every segment visibility graph has a cycle visiting every vertex exactly once. The accompanying caption allows such a cycle to cross itself and separately describes a cycle bounding a simple polygon. The precise segment visibility model and admissible configurations are missing. The registry labels this problem open; that label is supplied curation, not an independently verified assessment.

Sources

• Local UnsolvedMath registry, permanent ID $800543$, exact source problem code catalogue entry, title Visibility Graphs of Points, Segments and Polygons --- Conjecture 14. The supplied record attributes the problem to Ghosh and Goswami, gives proposed year 2010, and labels its status open. Its creation and update timestamps are both 2026-10-16T14:00:00Z; these are registry metadata, not independent mathematical verification. Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Conjecture 14. Supplied source URL: https://arxiv.org/abs/1012.5187. The record reports access on 2026-10-16 and extraction by arxiv_latex; this is supplied provenance, not a claim that the source was visited or independently checked for this draft.
• The supplied extraction includes a caption associated with fhamilton1.eps and the citation label [rit-cscf-90]. Neither the figure nor a bibliographic expansion of that label is supplied.