The Bar Visibility Number of a Graph
Yi-Wu Chang, Joan P. Hutchinson, Michael S. Jacobson, Jenő Lehel, Douglas B. West · SIAM Journal on Discrete Mathematics · 2004
The bar visibility number of a graph G, denoted b(G), is the minimum t such that G can be represented by assigning each vertex x the set S x of points in at most t horizontal segments in the plane so that uv $\in$ E(G) if and only if some point of S u sees some point of S v via a vertical segment of positive width unobstructed by assigned points. Among our results are the following: (1) Every planar graph has bar visibility number at most 2, which is sharp. (2) $r\le b(K_{m,n})\le r+1$, where $r=\big\lceil\frac{mn+4}{2m+2n}\big\rceil$. (3) $b(K_n)=\lceil{n/6}\rceil$. (4) If G has n vertices, then $b(G)\le \lceil{n/6}\rceil+2$.