Visibility Graphs of Points, Segments and Polygons — Problem 1

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph, given by its adjacency matrix. For distinct points $p,q\in{\mathbb{R}}^2$, write \[ (p,q)=\{(1-t)p+tq:0<t<1\} \] for their open line segment. For a finite set $P\subseteq{\mathbb{R}}^2$, its point visibility graph has vertex set $P$, with distinct $p,q\in P$ adjacent exactly when $(p,q)\cap P=\varnothing$. Collinear points are permitted; no general-position hypothesis is imposed.

Recognition problem (Ghosh--Goswami, Problem 1). Given $G$, determine whether there exists an injective map $f:V\to{\mathbb{R}}^2$ such that, for every pair of distinct vertices $u,v\in V$, \[ \{u,v\}\in E \quad\Longleftrightarrow\quad (f(u),f(v))\cap f(V)=\varnothing. \] Equivalently, determine whether $G$ is isomorphic to the visibility graph of some finite planar point set.

The supplied excerpt refers to an earlier definition of visibility that is not included in the record. The open-segment convention above, and the finite simple undirected graph convention, are standard interpretations requiring confirmation against the complete source. No running-time bound or coordinate representation is specified in the supplied question.

The source distinguishes recognition from characterization, which seeks properties characterizing visibility graphs, and reconstruction, which seeks an actual realizing point set. The stated task is recognition.

Short English statement

Given the adjacency matrix of a finite graph, decide whether its vertices can be represented by distinct points in the plane so that two vertices are adjacent exactly when no other representing point lies strictly between them. This uses the conventional point-visibility definition, whose earlier source definition is absent from the supplied excerpt.

Sources

• Local UnsolvedMath registry, permanent ID $800532$, source code catalogue entry, titled "Visibility Graphs of Points, Segments and Polygons --- Problem 1." The supplied record attributes the problem to Ghosh and Goswami, with proposed year 2010, and labels it open; that label is supplied metadata, not an independently verified mathematical status.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 1. Supplied source link: https://arxiv.org/abs/1012.5187. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance statements, not an independent source visit or verification.
• Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.