Chen, Guantao; Hutchinson, Joan P.; Keating, Ken; Shen, Jian Characterization of \([1,k]\)-bar visibility trees. (English) Zbl 1110.05104 Electron. J. Comb. 13, No. 1, Research paper R90, 12 p. (2006). Summary: 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 an 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. MSC: 05E25 Group actions on posets, etc. (MSC2000) 05C75 Structural characterization of families of graphs PDFBibTeX XMLCite \textit{G. Chen} et al., Electron. J. Comb. 13, No. 1, Research paper R90, 12 p. (2006; Zbl 1110.05104) Full Text: EuDML EMIS