Visibility Graphs of Points, Segments and Polygons — Problem 38

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph with $V=\{1,\ldots,n\}$. Its adjacency matrix is $A\in\{0,1\}^{n\times n}$, where $A_{ii}=0$ and, for distinct $i,j$, $A_{ij}=A_{ji}=1$ if and only if $\{i,j\}\in E$. A clique is a subset $C\subseteq V$ such that every two distinct vertices of $C$ are adjacent. Define \[ \omega(G)=\max\left\{|S|:S\subseteq V,\ \forall i,j\in S,\ i\ne j\Longrightarrow A_{ij}=1\right\}. \] Let $\mathcal V$ denote the class of visibility graphs intended in the supplied source. The excerpt discusses visibility inside a polygon, but does not specify the geometric objects represented by vertices, the permitted polygon class, or the visibility convention. Thus $\mathcal V$ remains an unresolved qualification of the statement.

Computational problem (source Problem 38). For every finite graph $G\in\mathcal V$, given only its adjacency matrix $A$, compute a clique $C\subseteq V$ with $|C|=\omega(G)$. The input is promised to be a visibility graph; no geometric realization is supplied. The excerpt specifies no running-time bound, so this is an optimization task whose intended algorithmic complexity target requires clarification.

The source states that a maximum clique corresponds to a largest empty convex polygon inside the corresponding polygon. The meaning of "empty" and the hypotheses needed for this correspondence are not supplied, so this observation is retained as a source assertion rather than used as an additional definition or an established equivalence. The source also reports that NP-hardness of this problem was not known in its 2010 discussion; this is a historical source qualification, not an independently verified current complexity assessment.

Short English statement

Given only the adjacency matrix of a graph promised to belong to the source's intended visibility-graph class, find a largest set of pairwise adjacent vertices. The exact visibility model and the desired running-time bound are unresolved in the supplied excerpt. This is a statement-only draft requiring human mathematical review.

Sources

• Local UnsolvedMath registry: permanent ID $800564$, exact source code catalogue entry; title: Visibility Graphs of Points, Segments and Polygons --- Problem 38. The supplied registry attributes the problem to Ghosh and Goswami, gives proposed year 2010, and labels its status "open". This status is supplied metadata, not independently verified.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 38, https://arxiv.org/abs/1012.5187. The supplied provenance records access on 2026-10-16 and extraction by arxiv_latex; these are source-provided provenance details, not a claim of independent access or verification.
• The excerpt cites reference labels ar-clec-85, deo-secp-90, and es-mcmcpvg-00 for algorithms computing largest empty convex polygons. It says that the first two take a point set as input and the third takes a polygon as input. Full bibliographic entries are absent from the supplied record.
• The excerpt attributes possible maximum-clique approaches using triangle-extendible ordering to Spinrad, reference label s-grep-03. Its description of that ordering as "essentially a transitive orientation" is a supplied informal characterization; neither a definition nor a full bibliographic entry is provided.