Characterization of \([1,k]\)-bar visibility trees
type: Item
instance of: scholarly article
title: Characterization of \([1,k]\)-bar visibility trees
zbMATH Open document ID: 1110.05104
author: Guantao Chen
author: Joan P. Hutchinson
author: Ken Keating
author: J. Shen
published in: The Electronic Journal of Combinatorics
publication date: 2007-03-12T00:00:00Z
full work available at URL: https://eudml.org/doc/127213
full work available at URL: v13i1r90.html
review text: 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.
Mathematics Subject Classification ID: 05E25
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 5132803
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5132803