Visibility Graphs of Points, Segments and Polygons — Problem 11

Definitions and mathematical statement

Let $G$ be a finite graph given by its adjacency matrix. For a set $S$ of pairwise disjoint line segments in ${\mathbb{R}}^2$, write $\operatorname{SVG}(S)$ for the segment visibility graph intended by the source.

The supplied excerpt does not define this construction: it does not specify whether graph vertices represent segments or their endpoints, which connecting segments establish visibility, or how boundary contacts and degenerate segments are treated. These conventions must be recovered from the source before the recognition predicate is fully specified; no particular convention is adopted here.

The requested recognition problem is to construct an algorithm that halts on every input graph $G$ and answers yes exactly when \[ \exists\, S\text{ a set of pairwise disjoint line segments in }{\mathbb{R}}^2 \quad G\cong\operatorname{SVG}(S). \] The excerpt does not explicitly restrict $S$ to be finite. The intended admissible families and the definition of $\operatorname{SVG}$ remain qualifications of this formulation. No running-time bound for the general recognition problem is specified.

For the supplied background, $K_5$ denotes the complete graph on five vertices. A graph $M$ is a minor of a graph $G$ if it can be obtained from $G$ by a sequence of vertex deletions, edge deletions, and edge contractions. The source attributes to Everette et al. a characterization of the segment visibility graphs having no $K_5$ minor and a polynomial-time recognition algorithm for that subclass. This is a supplied historical claim, not an independently verified assessment of the literature. The registry labels the general recognition problem open.

Short English statement

Given a graph by its adjacency matrix, decide whether it can be realized as the segment visibility graph of pairwise disjoint planar segments. The excerpt omits the precise visibility construction, so the intended realization predicate requires clarification. The open label and the reported result for the subclass with no $K_5$ minor are supplied source assessments.

Sources

• Local UnsolvedMath registry, permanent ID $800541$, source problem code catalogue entry, title "Visibility Graphs of Points, Segments and Polygons --- Problem 11." The supplied record attributes the problem to Ghosh and Goswami, with proposed year 2010, and labels it open. Upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82. The record was created and updated on 2026-10-16.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 11. Supplied source URL: https://arxiv.org/abs/1012.5187. The provenance records access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance statements, not a claim of independent access or verification.
• The supplied excerpt attributes the characterization and polynomial-time recognition of the subclass with no $K_5$ minor to "Everette et al.," reference label [ehkn-cgta2-2000]. No full bibliographic entry or separate URL for that reference is supplied.