\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Guantao Chen, Joan P. Hutchinson, Ken Keating and Jian Shen }
%
%
\medskip
\noindent
%
%
{\bf Characterization of $[1,k]$-Bar Visibility Trees}
%
%
\vskip 5mm
\noindent
%
%
%
%
A {\it 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 {\em
$[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.
\bye