Visibility Graphs of Points, Segments and Polygons — Problem 18

Definitions and mathematical statement

Let $\mathcal C_{\mathrm{seg}}$ denote the class called segment visibility graphs in the supplied source. The record does not provide its geometric definition; this notation therefore names the intended class without resolving its realization conventions.

Under the usual finite simple undirected graph convention, write $G=(V,E)$, where $V=\{1,\ldots,n\}$. Its adjacency matrix is $A\in\{0,1\}^{n\times n}$, with $A_{ij}=1$ exactly when $\{i,j\}\in E$. For $n\geq 3$, a Hamiltonian cycle is a cyclic ordering $(v_1,\ldots,v_n)$ containing every vertex exactly once and satisfying \[ \{v_i,v_{i+1}\}\in E\quad(1\leq i<n),\qquad \{v_n,v_1\}\in E. \]

First request (Problem 18). Construct an algorithm that, given only the adjacency matrix of a graph $G$ promised to belong to $\mathcal C_{\mathrm{seg}}$, outputs a Hamiltonian cycle in $G$ in time polynomial in $n$. No geometric realization is included in the stated input. The source requests a cycle outright: it does not specify an additional existence promise or an output for inputs without a Hamiltonian cycle. Under the convention above, graphs with fewer than three vertices have no Hamiltonian cycle; the intended treatment of such cases is unspecified.

Additional request in the supplied record. Given a segment visibility graph $G$ in adjacency matrix form, identify the edges of $G$ that correspond to segments of $S$. For an intended segment realization $S$, denote this distinguished edge set by \[ F_S=\{e\in E(G):e\text{ corresponds to a segment belonging to }S\}. \] The requested output is thus $F_S$, but the record neither defines $S$ nor supplies it as input. It also does not specify whether the output should describe a particular underlying realization, some compatible realization, or edges common to all compatible realizations. These alternatives cannot be identified from the supplied text. The additional request has no explicitly stated polynomial running-time requirement.

Short English statement

The first request asks for a polynomial-time algorithm that finds a Hamiltonian cycle from the adjacency matrix of a promised segment visibility graph. The appended request asks which graph edges represent the original segments. The supplied record omits the geometric visibility conventions, cycle-existence qualifications, and the intended interpretation of the underlying segment set $S$, so these remain unresolved.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $800547$, exact source code catalogue entry, titled "Visibility Graphs of Points, Segments and Polygons --- Problem 18," in the AMR Open Problem Lists collection. The 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 assessment.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 18. Supplied source URL: https://arxiv.org/abs/1012.5187.
• Supplied provenance reports access on 2026-10-16 and extraction method arxiv_latex. These are source-record provenance claims; no independent source visit or literature verification was performed. The supplied record places the Hamiltonian-cycle request inside an unsolved environment and appends the segment-identification request outside that environment.