Further Results on Bar k-Visibility Graphs

Abstract

A bar visibility representation of a graph G is a collection of horizontal bars in the plane corresponding to the vertices of G such that two vertices are adjacent if and only if the corresponding bars can be joined by an unobstructed vertical line segment. In a bar k-visibility graph, two vertices are adjacent if and only if the corresponding bars can be joined by a vertical line segment that intersects at most k other bars. Bar k-visibility graphs were introduced by Dean et al. [J. Graph Algorithms Appl., 11 (2007), pp. 45–59]. In this paper, we present sharp upper bounds on the maximum number of edges in a bar k-visibility graph on n vertices and the largest order of a complete bar k-visibility graph. We also discuss regular bar k-visibility graphs and forbidden induced subgraphs of bar k-visibility graphs.