Originators: Douglas West (presented by Douglas West - REGS 2011)
Definitions: A t-bar representation of a graph G assigns each vertex a set that is the union of at most t horizontal segments ("bars") in the plane, so that vertices are adjacent if and only if there is an unobstructed vertical line of sight (having positive width) joining the sets assigned to them. The graphs having such representations with k=1 are the bar visibility graphs. The visibility number of a graph G, written b(G), is the minimum t such that G has a t-bar representation.
Background: Bar visibility graphs have been well studied and characterized; they are the planar graphs having an embedding in which all vertices lie on a single face ([TT,W]). The visibility number was introduced in [CHJLW], where many results were proved. By following an Eulerian circuit through a graph obtained from G by adding one vertex adjacent to all vertices of odd degree in G, it is easy to show that b(G)≤⌈(Δ(G)+1)/2⌉. On the other hand, by applying Euler's Formula to the planar graph obtained by adding the lines of sight as edges and shrinking every bar to a vertex, one obtains b(G)≥(|E(G)|+4)/(2|V(G)|) when G is a triangle-free graph.
Question: What is the visibility number of the d-dimensional hypercube Qd?
Comments: The trivial upper and lower bounds from the background remarks are ⌈(d+1)/2⌉ and ⌈(d+1)/4⌉. Using the fact that b(Q3)=1, one can easily reduce the upper bound to ⌈(d+1)/3⌉. REGS students have produced a 2-bar representation of b(Q7)=1, thereby suggesting that the lower bound could in fact be optimal.
Similar behavior occurred for complete bipartite graphs. The argument from Euler's Formula yields b(Km,n)≥⌈(mn+4)/(2m+2n)⌉. In [CHJLW], it was proved that the actual value is within 1 of this, and Cao [C] showed that the trivial lower bound is exactly correct.
References:
[C] W. Cao, PhD thesis, University of Illinois, 2006.
[CHJLW] Y.-W. Chang, J.P. Hutchinson, M.S. Jacobson, J. Lehel, and D.B. West,
The visibility number of a graph,
SIAM J. Discrete Math. 148 (3) (2004), 462-471.
[TT] R. Tamassia and I.G. Tollis, A unified approach to visibility
representations of planar graphs, Discrete Comput. Geom., 1 (4) (1986), 321-341.
[W] S. K. Wismath, Characterizing bar line-of-sight graphs, In Proc. 1st Ann.
ACM Symp. Comput. Geom., 1985, 147-152.