
doi: 10.7155/jgaa.00157
Summary: 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 \textit{A. M. Dean, W. Evans, E. Gethner, J. D. Laison, M. A. Safari} and \textit{W. T. Trotter} [J. Graph Algorithms Appl. 11, No. 1, 45-59 (2007; Zbl 1161.68651)] 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.
Graph theory (including graph drawing) in computer science
Graph theory (including graph drawing) in computer science
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 12 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
