Visibility Graphs of Points, Segments and Polygons — Problem 19

Definitions and mathematical statement

Let $G=(V,E)$ be a graph in the intended graph domain. A representation by horizontal bars of a common positive length has bars \[ B_v=[a_v,a_v+\ell]\times\{h_v\},\qquad a_v,h_v\in{\mathbb{R}},\quad v\in V, \] where the same $\ell>0$ is used for every vertex. A uniform scaling permits the normalization $\ell=1$.

Fix the admissibility and visibility conventions for the underlying bar visibility representation. Write $\operatorname{Vis}(B_u,B_v;\mathcal B)$ for visibility between two bars in the complete family $\mathcal B=(B_v)_{v\in V}$, according to those conventions. In the undirected interpretation with adjacency represented exactly by visibility, the representation must satisfy \[ \{u,v\}\in E \quad\Longleftrightarrow\quad \operatorname{Vis}(B_u,B_v;\mathcal B) \qquad(u,v\in V,\ u\ne v). \] A graph admitting an admissible representation of this kind with all bars of equal positive length is a unit bar visibility graph.

Problem (Ghosh--Goswami, 2010, Problem 19). Find necessary and sufficient graph-theoretic conditions characterizing the unit bar visibility graphs.

Unresolved qualifications. The supplied excerpt does not define the underlying bar visibility convention. In particular, it does not specify the admissible intersections or placements of bars, whether visibility requires an unobstructed vertical corridor of positive width or merely a vertical line segment, or the treatment of endpoint contacts. It also does not explicitly specify the graph domain or whether every visibility must correspond to an edge. The displayed equivalence records the exact-adjacency, undirected interpretation conditionally; these conventions require confirmation before this becomes a fully specified characterization problem.

Short English statement

Characterize the graphs that admit a bar visibility representation in which every horizontal bar has the same positive length. The supplied excerpt leaves the underlying visibility conventions and graph domain unspecified, so those qualifications require review.

Sources

• Local UnsolvedMath registry: permanent ID $800548$, exact source problem code catalogue entry, title Visibility Graphs of Points, Segments and Polygons --- Problem 19. The supplied record attributes the problem to Ghosh and Goswami, with proposed year 2010, and labels it open; that label is supplied registry metadata, not an independently verified mathematical status.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 19. Supplied source URL: https://arxiv.org/abs/1012.5187. The provenance records access on 2026-10-16 and extraction method arxiv_latex; these are supplied provenance statements, not a claim of independent source access.
• The supplied statement cites special-class characterization results using the reference labels chks-cbvt-2006, dgh-unvl-2004, and dv-ubvg-2003. Their bibliographic entries are not supplied. Its assertion that no characterization is known for general graphs is preserved as a claim of the supplied source, not an updated literature assessment.