Visibility Graphs of Points, Segments and Polygons — Problem 26

Definitions and mathematical statement

For a finite simple undirected graph $G=(V,E)$, its thickness is \[ \theta(G)=\min\left\{t\in{\mathbb{Z}}_{\geq 0}:E=E_1\cup\cdots\cup E_t,\ (V,E_i)\text{ is planar for every }i\right\}. \] The planar drawings of the graphs $(V,E_i)$ need not share vertex positions. Equivalently, the edges may be partitioned into planar subgraphs.

The supplied record does not define a bar $k$-visibility representation. A provisional interpretation is a representation by finitely many pairwise disjoint, nondegenerate horizontal line segments, one for each vertex. Two vertices are adjacent if and only if their bars are joined by a vertical rectangle of positive width whose horizontal sides lie on those bars and whose open interior meets at most $k$ other bars. Write $\mathcal B_k$ for the class represented under this interpretation. The visibility conventions must be checked against the cited source before this interpretation is accepted.

For a positive integer $k$, set \[ T(k)=\sup\{\theta(G):G\in\mathcal B_k\}. \] The supplied source reports the universal bound \[ T(k)\leq 2k(9k-1). \] Its question is to improve this upper bound: seek a sharper function $U(k)$ such that \[ \forall k\in{\mathbb{Z}}_{\geq1}\ \forall G\in\mathcal B_k,\qquad \theta(G)\leq U(k). \] The source does not specify the range of $k$ on which strict improvement is required, or whether the intended improvement concerns the leading order, constants, or individual values. The positive-integer domain above is provisional: the source states no domain for $k$, and its displayed bound cannot include $k=0$ for graphs with edges.

As background, the record attributes to Dean et al. an upper bound of $4$ for bar $1$-visibility graphs and a conjectured upper bound of $2$. It reports that Felsner and Massow disproved that conjecture by constructing a bar $1$-visibility graph of thickness $3$. It also reports their algorithm partitioning the edges of an unspecified special class into two planar graphs, describing that class as having thickness $2$. Such a partition establishes an upper bound of $2$; the record supplies neither the definition of that class nor the qualifications needed for an equality claim. These are supplied historical assertions, not independently verified results.

Short English statement

Improve the reported bound $2k(9k-1)$ on the thickness of bar $k$-visibility graphs. Thickness is the minimum number of planar subgraphs needed to cover all edges. The supplied record leaves the visibility conventions, the domain of $k$, and the intended strength of improvement unspecified; the formulation above uses an explicitly provisional interpretation.

Sources

• Local UnsolvedMath registry: permanent ID $800552$, source problem code catalogue entry, title "Visibility Graphs of Points, Segments and Polygons --- Problem 26." The supplied record attributes the problem to Ghosh and Goswami, with proposed year $2010$, and labels it open. That status is supplied registry information, not an independently verified current assessment.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 26: https://arxiv.org/abs/1012.5187. The supplied provenance records access on 2026-10-16 and extraction method arxiv_latex; this is supplied dated provenance, not a claim of independent source access or verification.
• Dean et al., source reference label [deglst-bvg-2007], cited for the thickness problem, the reported bar $1$-visibility upper bound, and the disproved conjecture. Full bibliographic details are absent from the supplied record.
• Source reference label [mos-tgs-1998], cited for background on exact thickness values. Authors and full bibliographic details are absent from the supplied record.
• Felsner and Massow, source reference label [fw-tbvg-2007], cited for a thickness-$3$ example and the two-planar-subgraph algorithm for a special class. Full bibliographic details and a definition of that class are absent from the supplied record.