Visibility Graphs of Points, Segments and Polygons — Problem 17

Definitions and mathematical statement

Let $\mathcal V_{17}$ denote the class called segment visibility graphs in Problem 17 of the supplied source. The record does not define this geometric graph class or specify the admissible segment configurations and visibility convention. Thus the algorithmic statement below retains the source's intended class as a parameter; its complete geometric specification requires clarification from the source.

For a finite simple undirected graph $G=(V,E)$ with $n=|V|\geq 3$, a Hamiltonian cycle is a cyclic ordering $(v_1,\ldots,v_n)$ of all vertices, each appearing exactly once, such that \[ \{v_i,v_{i+1}\}\in E\quad(1\leq i<n), \qquad \{v_n,v_1\}\in E. \] The adjacency matrix of $G$, after labeling $V=\{1,\ldots,n\}$, is the matrix $A_G\in\{0,1\}^{n\times n}$ with $(A_G)_{ij}=1$ exactly when $\{i,j\}\in E$.

Problem. Find an algorithm and a polynomial $p$ such that, for every $n\geq 3$ and every $G\in\mathcal V_{17}$ on $n$ vertices, the algorithm, given only $A_G$, outputs a Hamiltonian cycle of $G$ within $p(n)$ computational steps. A realizing segment configuration $S$, its coordinates, and an embedded realization are not supplied. Membership in $\mathcal V_{17}$ is an input promise; recognition of that class is not requested.

The source asks for a cycle on every promised input, rather than asking merely to decide whether one exists. Its intended graph class and geometric hypotheses must therefore support that existence requirement; the supplied record does not state those hypotheses explicitly. The restriction $n\geq 3$ uses the usual simple-graph cycle convention. The source does not specify how smaller graphs are to be handled.

Supplied context. The source states that an algorithm of Hoffmann and Tóth, cited there as [ht-sevg-2003], takes $S$ as input and finds a Hamiltonian circuit in an embedded segment visibility graph $G'$. It then asks for a polynomial-time algorithm when only the abstract graph $G$ is supplied. Its accompanying statement that no segment visibility graph reconstruction algorithm is known is historical source context, not an independently verified current literature assessment.

Short English statement

Given only the adjacency matrix of a graph promised to be a segment visibility graph in the sense of the cited Problem 17, find a Hamiltonian cycle in polynomial time, without receiving a realizing segment configuration. The supplied record leaves the geometric graph definition, required configuration hypotheses, and small-input conventions unresolved.

Sources

• Local UnsolvedMath registry, permanent ID $800546$, exact source code catalogue entry, titled Visibility Graphs of Points, Segments and Polygons --- Problem 17. The supplied record attributes the problem to Ghosh and Goswami, with proposed year 2010, and labels it open. This label is supplied registry metadata, not an independently verified mathematical or literature assessment. The record was updated on 2026-10-16 and identifies upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 17. Supplied source URL: https://arxiv.org/abs/1012.5187. The supplied provenance records access on 2026-10-16 and extraction method arxiv_latex; these are supplied provenance statements, not a claim of independent access or verification here.
• Hoffmann and Tóth, cited in the supplied excerpt under the reference label [ht-sevg-2003], for the algorithm taking a segment configuration $S$ and finding a Hamiltonian circuit in an embedded segment visibility graph $G'$. No full bibliographic entry or separate URL for this reference is supplied.