Visibility Graphs of Points, Segments and Polygons — Problem 27

Definitions and mathematical statement

For a finite graph $G$, let $\mathcal D(G)$ be the set of plane drawings in which vertices are distinct points and edges are simple arcs joining their endpoints, with edge interiors avoiding vertices. Use drawings in general position: interior intersections are transverse crossings, there are finitely many crossings, and no three edge interiors meet at one point. The crossing number is \[ \operatorname{cr}(G)=\min_{D\in\mathcal D(G)}\#\{\text{interior edge crossings in }D\}. \] This uses the usual finite-graph drawing convention; the supplied record does not explicitly specify the graph category.

Let $\mathcal B_k$ denote the class called bar $k$-visibility graphs in the source. The requested extremal quantity is \[ \max\{\operatorname{cr}(G):G\in\mathcal B_k\}, \] provided that this maximum exists. The question is to determine the largest crossing number in this class.

The supplied record does not define bar $k$-visibility, specify the admissible values of $k$, or impose a number of vertices or another size bound. Thus $\mathcal B_k$ remains a source-dependent, unresolved part of the formulation. In particular, no fixed-order restriction may be silently inserted, and existence or finiteness of the displayed maximum is not asserted. A fully specified extremal problem requires clarification of these points.

Short English statement

Determine the largest possible crossing number of a bar $k$-visibility graph. The supplied record leaves the visibility model, the range of $k$, and any intended graph-size restriction unspecified, so the exact extremal target requires clarification.

Sources

• Local UnsolvedMath registry, supplied complete source record: permanent ID $800553$, exact source code catalogue entry, title Visibility Graphs of Points, Segments and Polygons --- Problem 27. The registry attributes the problem to Ghosh and Goswami, with proposed year 2010, and labels it open; this status is supplied metadata, not an independently verified mathematical assessment.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 27. 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 details, not a claim of independent consultation or verification.