Visibility Graphs of Points, Segments and Polygons — Problem 41

Definitions and mathematical statement

The supplied source does not specify the geometric visibility model or the input-size parameter. Consequently, the following expresses the requested coordinate bound conditionally, without selecting these missing conventions.

Let $\mathcal M$ denote the intended geometric visibility model, including its admissible configurations, visibility rule, and degeneracy conventions. Suppose a configuration $P$ in this model is specified by endpoints $p_1,\ldots,p_m\in{\mathbb{R}}^d$, where the dimension $d$ is fixed by the model, and write $\operatorname{Vis}_{\mathcal M}(P)$ for its visibility graph. Under the interpretation that the size parameter is the number $n$ of graph vertices, the question is whether there exists a polynomial $q$, independent of the graph, such that every finite graph $G$ realizable in $\mathcal M$, with $|V(G)|=n$, has an admissible realization $P$ satisfying \[ \operatorname{Vis}_{\mathcal M}(P)\cong G,\qquad p_i\in{\mathbb{Z}}^d,\qquad \left\lceil\log_2\left(2+|(p_i)_j|\right)\right\rceil\le q(n) \quad(1\le i\le m,\ 1\le j\le d). \] The displayed bound measures binary coordinate length up to a constant allowance for a sign. The polynomial must be uniform over all realizable graphs in the intended model.

The model $\mathcal M$, dimension, relationship between endpoints and graph vertices, and intended size parameter remain unresolved in the supplied excerpt. Thus this is a conditional statement template requiring clarification, rather than a fully specified geometric conjecture. The source attributes an exponential integer-coordinate requirement to Lin and Skiena, but supplies no precise lower-bound formulation. It also states that a polynomial coordinate-bit bound would place visibility-graph recognition in $\mathrm{NP}$; the excerpt does not specify the model, certificate-size assumptions, or verification procedure underlying that implication.

Short English statement

Does every visibility graph admit a realization whose endpoint coordinates are integers of polynomial binary length? The supplied record labels this question open, but does not specify the visibility model or the parameter governing the polynomial. Those choices require human review.

Sources

• Local UnsolvedMath registry, permanent ID $800567$, exact source problem code catalogue entry; title: Visibility Graphs of Points, Segments and Polygons --- Problem 41. The registry attributes the problem to Ghosh and Goswami (2010) and supplies the status open; this status is not independently verified here.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 41. Supplied source URL: https://arxiv.org/abs/1012.5187. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance claims, not a claim of source access in preparing this draft.
• Lin and Skiena, reference label [ls-cavg-95] in the supplied excerpt, cited there for an exponential integer-coordinate requirement. Full bibliographic details and the precise theorem are not supplied.
• Reference label [s-grep-03] in the supplied excerpt, cited there for the connection with recognition in $\mathrm{NP}$. Author, title, and full bibliographic details are not supplied.