Characterization of \([1,k]\)-bar visibility trees
The electronic journal of combinatorics, Tome 13 (2006)
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.
@article{10_37236_1116,
author = {Guantao Chen and Joan P. Hutchinson and Ken Keating and Jian Shen},
title = {Characterization of \([1,k]\)-bar visibility trees},
journal = {The electronic journal of combinatorics},
year = {2006},
volume = {13},
doi = {10.37236/1116},
zbl = {1110.05104},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1116/}
}
TY - JOUR AU - Guantao Chen AU - Joan P. Hutchinson AU - Ken Keating AU - Jian Shen TI - Characterization of \([1,k]\)-bar visibility trees JO - The electronic journal of combinatorics PY - 2006 VL - 13 UR - http://geodesic.mathdoc.fr/articles/10.37236/1116/ DO - 10.37236/1116 ID - 10_37236_1116 ER -
Guantao Chen; Joan P. Hutchinson; Ken Keating; Jian Shen. Characterization of \([1,k]\)-bar visibility trees. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1116
Cité par Sources :