Further Results on Arc and Bar k-Visibility Graphs
Mehtaab Sawhney
Massachusetts Institute of Technology
Jonathan Weed
Massachusetts Institute of Technology
Abstract
We consider visibility graphs involving bars and arcs in which lines of sight can pass through at most $k$ objects. We prove a new edge bound for arc $k$-visibility graphs, provide maximal constructions for arc visibility graphs and semi-arc $k$-visibility graphs, and give a complete characterization of semi-arc visibility graphs. We further show that the family of arc $i$-visibility graphs is never contained in the family of bar $j$-visibility graphs for any $i$ and $j$, and that the family of bar $i$-visibility graphs is not contained in the family of bar $j$-visibility graphs for $i \neq j$. We also give the first thickness bounds for arc and semi-arc $k$-visibility graphs. Finally, we introduce a model for random semi-bar and semi-arc $k$-visibility graphs and analyze its properties.
