Characterization of $[1,k]$-Bar Visibility Trees

A unit bar-visibility graph is a graph whose vertices can be represented in the plane by disjoint horizontal unit-length bars such that two vertices are adjacent if and only if there is a unobstructed, non-degenerate, vertical band of visibility between the corresponding bars. We generalize unit bar-visibility graphs to $[1,k]$-bar-visibility graphs by allowing the lengths of the bars to be between $1/k$ and $1$. We completely characterize these graphs for trees. We establish an algorithm with complexity $O(kn)$ to determine whether a tree with n vertices has a $[1,k]$-bar-visibility representation. In the course of developing the algorithm, we study a special case of the knapsack problem: Partitioning a set of positive integers into two sets with sums as equal as possible. We give a necessary and sufficient condition for the existence of such a partition.