Visibility Graphs of Points, Segments and Polygons — Problem 28

Definitions and mathematical statement

For a graph $G$, let $\operatorname{cr}(G)$ denote its crossing number: the minimum number of edge crossings in a drawing of $G$ in the plane, with crossings counted away from vertices under the usual general-position drawing conventions. The source also defines the genus of $G$ as \[ \gamma(G)=\min\{g\in{\mathbb{Z}}_{\ge 0}:G\text{ embeds in a surface of genus }g\}. \] Here an embedding has no edge crossings. The source does not specify whether surfaces are orientable or nonorientable; this convention must be fixed before $\gamma$ is unambiguous.

Let $\mathcal B_k$ denote the class called bar $k$-visibility graphs in the supplied source. This is a placeholder for the source's graph class: the supplied record does not define a bar representation, the visibility and obstruction rules, or the permitted values of $k$. Those missing conventions must be supplied before this class is precisely determined.

Questions (Problem 28). For each permitted value of $k$, determine the largest crossing number and the largest genus of a graph in $\mathcal B_k$. Once the class and surface convention have been fixed, the unrestricted extremal quantities can be expressed as \[ C(k)=\sup\{\operatorname{cr}(G):G\in\mathcal B_k\}, \qquad H(k)=\sup\{\gamma(G):G\in\mathcal B_k\}, \] allowing $+\infty$ if the corresponding values are unbounded. This supremum notation records the possibility that no finite largest value exists; it does not assert boundedness or attainment.

Unresolved scope. The supplied questions place no bound on the number of vertices and do not specify the graph domain, including finiteness and simplicity. If the intended question instead concerns graphs with a fixed number $n$ of vertices, its extremal quantities would be \[ C(n,k)=\sup\{\operatorname{cr}(G):G\in\mathcal B_k,\ |V(G)|=n\}, \qquad H(n,k)=\sup\{\gamma(G):G\in\mathcal B_k,\ |V(G)|=n\}. \] The supplied record does not establish that this order-dependent formulation is intended. Consequently, the display above is only a possible clarification, not a replacement for the source questions.

Short English statement

Problem 28 asks how large the crossing number and genus of a bar $k$-visibility graph can be. The supplied registry labels the record open. A precise formulation still requires the definition of bar $k$-visibility, the range of $k$, the graph and surface conventions, and clarification of whether the number of vertices is fixed.

Sources

• Local UnsolvedMath registry, permanent ID $800554$, exact source problem code catalogue entry, title Visibility Graphs of Points, Segments and Polygons --- Problem 28. The supplied record attributes the problem to Ghosh and Goswami, with proposed year 2010, and labels its status open; that label is supplied curation, not an independently verified mathematical or literature assessment.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 28. Supplied source URL: https://arxiv.org/abs/1012.5187. The background reports access on 2026-10-16 and extraction by arxiv_latex; these provenance details are supplied and were not independently verified here.
• The supplied statement includes the crossing-number question inside an unsolved environment and then gives the genus definition and genus question immediately afterward. Both questions are retained in this draft.