2015/08/11 by Gaub, Emily, Rose, Michelle, Wenger, Paul S.
#05C62 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1508.02616
A t-unit-bar representation of a graph G is an assignment of sets of at most t horizontal unit-length segments in the plane to the vertices of G so that (1) all of the segments are pairwise nonintersecting, and (2) two vertices x and y are adjacent if and only if there is a vertical channel of positive width connecting a segment assigned to x and a segment assigned to y that intersects no other segment. The unit bar visibility number of a graph G, denoted ub(G), is the minimum t such that G has a t-unit-bar visibility representation. Our results include a linear time algorithm that determines ub(T) when T is a tree, bounds on ub(Km,n) that determine ub(Km,n) asymptotically when n and m are asymptotically equal, and bounds on ub(Kn) that determine ub(Kn) exactly when n≡ 1,2\pmod 6.