Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00393
The Unit Bar Visibility Number of a Graph
Emily Gaub,
Michelle Rose, and
Paul S. Wenger
Vol. 20, no. 2, pp. 269297, 2016. Regular paper.
Abstract A $t$unitbar representation of a graph $G$ is an assignment of sets of at most $t$ horizontal unitlength 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$unitbar 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

Journal Supporters
