Originators: Paul Wenger (presented by P. Wenger - REGS 2010)
Definitions: A bar in the plane is a horizontal segment; a multibar is a set that is a disjoint union of bars. From a family of multibars, the visibility graph has a vertex for each multibar, with vertices adjacent when there is an vertical line of sight joining the corresponding multibars that does not intersect any other sets in the family. A (multi)bar visibility representation of a graph G is a family of multibars for which G is the visibility graph.
The bar visibility number of a graph G, written b(G), is the minimum, over all such representations of G, of the maximum number of bars used for one vertex. The total bar visibility number, written B(G), is the minimum of the total number of bars used for all the vertices.
Background: The graphs with bar visibility number 1 are the bar visibility graphs; they were characterized by Tamassia & Tollis [TT]; see also [W] and [H]. They are the planar graphs having embeddings such that all cut-vertices appear on the unbounded face. Planar graphs are rare, and defining the parameters above allows us to discuss visibility representations of all graphs, judged by how "complex" the representations need to be.
Many representation parameters seek to minimize the maximum usage of a vertex. In such situations, it may also be of interest to minimize the average usage, which corresponds to minimizing the total usage. (Such parameters include interval number, linear discrepancy of posets, etc.). Always B(G)≤nb(G) when G has n vertices; the problem is to understand how good the trivial upper bound is.
Question 1: For what n-vertex graphs G is B(G) significantly smaller than nb(G)?
Comments: Chang, Hutchinson, Jacobson, Lehel, & West [CHJLW] studied extremal problems for b(G). In particular, they proved that b(Kn) = ⌈n/6⌉ and that b(G) ≤ ⌈n/6⌉+2 whenever G has n vertices. Also, Cao [C] determined b(Kr,s). The parameter has not been greatly studied for other classes of graphs.
Conjecture 2: b(G) ≤ ⌈n/6⌉ whenever G has n vertices.
Comments: The lower bounds for these results come from a counting argument based on shrinking the bars in the representation to obtain a planar graph H whose edges correspond to edges of the original graph G. However, each vertex of G is represented in H by a vertex for each of its bars; G is obtained from H by merging copies of the same vertex in G and deleting multiple copies of edges that may arise. If the representation has t bars, and G has m edges, then H is a planar graph with t vertices and at least m edges. By the standard edge bound for planar graphs, m≤3t-6, or t≥(m+6)/3. (For bipartite graphs, we obtain t≥(m+4)/2.) This yields b(Kn) ≥n/6 and B(Kn) ≥n(n-1)/6.
Hence over the class of all n-vertex graphs the extremal problem for B(G) is not very interesting. On the other hand, it may be quite interesting for classes such as n-vertex planar graphs, where [CHJLW] showed that the maximum of b(G) is 2, but the basic argument above shows only that B(G) may be as large as the trivial value n.
Question 3: What is the maximum of B(G) over n-vertex planar graphs or over other sparse families of n-vertex graphs such as k-trees? When is it larger than the lower bound 2+|E(G)|/3?
References:
[CHJLW]
Chang, Yi-Wu; Hutchinson, Joan P.; Jacobson, Michael S.; Lehel, Jenö;
West, Douglas B.; The bar visibility number of a graph.
SIAM J. Discrete Math. 18 (2004/05), no. 3, 462--471
[H] Hutchinson, Joan P.; A note on rectilinear and polar visibility graphs.
Discrete Appl. Math. 148 (2005), no. 3, 263--272.
[TT] R. Tamassia and I. G. Tollis, A unified approach to visibility
representations of planar graphs, Discrete Comput. Geom., 1 (1986), pp.
321--341.
[W] S. Wismath, Characterizing bar line-of-sight graphs, in Proceedings of the
1st ACM Symposium Comput. Geom. Assoc. Comp. Mach., Baltimore, MD, 1985, ACM,
New York, pp. 147--152.