Parameters of Bar k-Visibility Graphs
DOI:
https://doi.org/10.7155/jgaa.00157Abstract
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.Downloads
Download data is not yet available.
Downloads
Published
2008-01-01
How to Cite
Felsner, S., & Massow, M. (2008). Parameters of Bar k-Visibility Graphs. Journal of Graph Algorithms and Applications, 12(1), 5–27. https://doi.org/10.7155/jgaa.00157
Issue
Section
Articles
Categories
License
Copyright (c) 2008 Stefan Felsner, Mareike Massow
This work is licensed under a Creative Commons Attribution 4.0 International License.