The Unit Bar Visibility Number of a Graph

Abstract

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(K_{m,n})$ that determine $ub(K_{m,n})$ asymptotically when $n$ and $m$ are asymptotically equal, and bounds on $ub(K_n)$ that determine $ub(K_n)$ exactly when $n\equiv 1,2\pmod 6$