The Unit Bar Visibility Number of a Graph
Emily Gaub, Michelle Rose, and Paul S. Wenger
Vol. 20, no. 2, pp. 269-297, 2016. Regular paper.
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$
Submitted: September 2015.
Reviewed: December 2015.
Revised: February 2016.
Accepted: March 2016.
Final: March 2016.
Published: April 2016.
Communicated by William S. Evans
article (PDF)