Visibility Graphs of Points, Segments and Polygons — Problem 39

Definitions and mathematical statement

For a finite simple undirected graph $G=(V,E)$, a clique is a set $C\subseteq V$ such that $\{u,v\}\in E$ for every pair of distinct vertices $u,v\in C$. A maximum clique is a clique of largest cardinality.

The principal task in the supplied record is: given the adjacency matrix of a graph $G$ promised to be a visibility graph, output a set $C\subseteq V$ satisfying \[ \left(\forall u,v\in C,\ u\ne v\Longrightarrow \{u,v\}\in E\right) \quad\text{and}\quad |C|=\max\left\{|D|:D\subseteq V\text{ is a clique of }G\right\}. \] Only the adjacency matrix is specified as input; a geometric representation is not supplied. The record does not specify which class of visibility graphs is intended, or an explicit running-time requirement for this maximum-clique task. These omissions prevent a fully specified algorithmic problem.

The record also appends a question asking whether one can determine in polynomial time if a set of vertices of a visibility graph has a triangle-extendible ordering. Interpreting the vertex set as a specified subset $S\subseteq V$, the intended question is whether there exists an ordering of $S$ satisfying that property. However, the record provides neither a definition of triangle-extendible ordering nor the conditions under which it is evaluated. Consequently, this appended question remains an incomplete decision-problem specification; its relationship to the maximum-clique task is also unspecified.

Short English statement

Given only the adjacency matrix of a visibility graph, find a largest set of pairwise adjacent vertices. An appended question asks for a polynomial-time test for the existence of a triangle-extendible ordering of a vertex set. The intended visibility class, the ordering property, and the relationship between these two tasks require clarification.

Sources

• Local UnsolvedMath registry, permanent ID $800565$, source problem code catalogue entry, title: Visibility Graphs of Points, Segments and Polygons --- Problem 39. The registry attributes the problem to Ghosh and Goswami, with proposed year 2010, and labels it open. These are supplied registry labels, not independently verified mathematical or historical assessments.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 39. Supplied source URL: https://arxiv.org/abs/1012.5187. The source record reports access on 2026-10-16 and extraction by arxiv_latex; these provenance details are supplied and have not been independently verified here.