Visibility Graphs of Points, Segments and Polygons — Conjecture 15

Definitions and mathematical statement

For an abstract graph $G$, a Hamiltonian cycle is a cycle that visits every vertex of $G$ exactly once, apart from repeating its initial vertex to close the cycle.

The supplied record attributes the following conjecture to Ghosh and Goswami (2010), identifying it as Conjecture 15:

Every segment visibility graph $G$ contains a Hamiltonian cycle $C$ that corresponds to a Hamiltonian circuit in the embedded segment visibility graph $G'$.

The intended quantifiers are universal over the segment visibility graphs covered by the source and existential over the cycle $C$. The notation $G'$ denotes the embedded segment visibility graph associated with $G$ in the source's intended construction.

This remains an unresolved formulation: the supplied record does not define a segment visibility graph, the associated embedded graph $G'$, or the correspondence between a cycle in $G$ and a Hamiltonian circuit in $G'$. In particular, the abstract definition of a Hamiltonian cycle above does not determine what the embedded circuit must visit or what geometric constraints it must satisfy. The admissible segment configurations and any restrictions needed for small or degenerate configurations are also unspecified. These source-dependent definitions and hypotheses must be recovered before the conjecture can be made self-contained; no particular visibility or embedding convention is imposed here.

Short English statement

The supplied conjecture asks whether every segment visibility graph has a Hamiltonian cycle that represents a Hamiltonian circuit in its associated embedded segment visibility graph. The supplied record labels the problem open. Its visibility, embedding, correspondence, and admissibility conventions are missing, so this is a statement-only draft requiring human mathematical review.

Sources

• Local UnsolvedMath registry: permanent ID $800544$, source problem code catalogue entry; title: "Visibility Graphs of Points, Segments and Polygons --- Conjecture 15." The supplied record gives Ghosh and Goswami as proposers, the year 2010, and the status open; this status is supplied registry metadata, not an independently verified assessment.
• Supplied source: Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Conjecture 15, https://arxiv.org/abs/1012.5187. The supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance details; the source has not been independently visited or verified for this draft.