Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Fourteenth International Symposium on Graph Drawing, GD 2006
DOI: 10.7155/jgaa.00157
Parameters of Bar k-Visibility Graphs
Vol. 12, no. 1, pp. 5-27, 2008. Regular paper.
Abstract
Bar k-visibility graphs are graphs admitting a representation in
which the vertices correspond to horizontal line segments, called
bars, and the edges correspond to vertical lines of sight which can
traverse up to k bars. These graphs were introduced by Dean et
al. [] who conjectured that bar 1-visibility graphs have
thickness at most 2. We construct a bar 1-visibility graph having
thickness 3, disproving their conjecture. Furthermore, we define semi
bar k-visibility graphs, a subclass of bar k-visibility graphs, and show tight
results for a number of graph parameters including chromatic number, maximum
number of edges and connectivity. Then we present an algorithm partitioning the
edges of a semi bar 1-visibility graph into two plane graphs, showing that for
this subclass the (geometric) thickness is indeed bounded by 2.
|
Journal Supporters
|