2016/01/06 by Mehtaab Sawhney, Sawhney, Mehtaab, Jonathan Weed +1
Computer Science · Mathematics · #05C62 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C62
paper · pdf · doi:10.48550/arxiv.1601.01231
20 pages
arxiv created 2016/01/06 · arxiv updated 2016/01/07
We consider visibility graphs involving bars and arcs in which lines of sight can pass through up to k objects. We prove a new edge bound for arc k-visibility graphs, provide maximal constructions for arc and semi-arc k-visibility graphs, and give a complete characterization of semi-arc visibility graphs. We 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 ≠ 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.