Visibility Graphs of Points, Segments and Polygons — Problem 42

Definitions and mathematical statement

The supplied source asks: "Give a tight bound (with respect to order notation) on the number of bits used in an optimal covering set of a visibility graph."

A precise formulation requires a specified class $\mathcal G$ of visibility graphs, a definition of the admissible covering sets $\mathcal C(G)$ for each $G\in\mathcal G$, an encoding of those sets, an optimality criterion, and a size parameter. These are not supplied.

For example, conditional on optimality meaning minimum encoded length, let $\ell_G(C)$ denote the length in bits of the specified encoding of $C\in\mathcal C(G)$. Provided the family is nonempty and these lengths are defined, the corresponding quantity would be \[ b(G)=\min_{C\in\mathcal C(G)}\ell_G(C). \] If a worst-case bound in terms of a specified size parameter $s(G)$ is intended, one could then define \[ B(n)=\sup\{b(G):G\in\mathcal G,\ s(G)=n\} \] for nonempty size classes, and ask for an explicit function $f$ such that $B(n)=\Theta(f(n))$ as $n\to\infty$ through the relevant sizes. This is only a conditional template, not a resolved interpretation of the source. In particular, the source does not establish that encoded length is the criterion defining an optimal covering set, that worst-case complexity is intended, or that the parameter is the number of graph vertices. The missing definitions prevent a unique, fully quantified mathematical statement.

Short English statement

Problem 42 asks for a tight asymptotic bound on the bits needed by an optimal covering set of a visibility graph. The supplied record does not define covering sets, their encoding or optimality, the visibility-graph class, or the asymptotic parameter, so the intended bound cannot yet be stated precisely.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $800568$, exact source problem code catalogue entry, title "Visibility Graphs of Points, Segments and Polygons --- Problem 42." The registry attributes the problem to Ghosh and Goswami, with proposed year 2010.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 42. 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 independent source verification.
• The supplied registry labels the problem "open" and records an update on 2026-10-16. This is a supplied curation label, not an independently verified assessment of the mathematical literature.