Characterization of [1,k]-bar visibility trees

MaRDI QIDQ870007zbMATH OpenFDO

Authors Guantao Chen, Joan P. Hutchinson, Ken Keating, J. Shen

Publication date 12 March 2007

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/127213, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r90.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

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.

Recommendations

• The unit bar visibility number of a graph
• Thickness of Bar 1-Visibility Graphs
• scientific article; zbMATH DE number 2068172
• Bar k-Visibility Graphs
• Parameters of Bar k-Visibility Graphs

Cited in

(2)

• The unit bar visibility number of a graph
• scientific article; zbMATH DE number 2068172 (Why is no real title available?)

This page was built for publication: Characterization of \([1,k]\)-bar visibility trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870007)