Sliding column model for t-unit bar visibility representations of graphs.

A bar visibility representation of a graph G is an assignment of the vertices of G to distinct horizontal line segments in the plane so that two vertices are adjacent in G if and only if there is an uninterrupted vertical channel of positive width that joins the bars corresponding to those vertices. A bar visibility representation is called a unit bar visibility representation if every bar has the same length. If each vertex is assigned to t distinct bars of the same length in a unit bar visibility representation then the representation is called t -unit bar visibility representation. In this paper, we introduce a "sliding column model" for t -unit bar visibility representation and show that every graph of maximum degree Δ has a t -unit bar visibility representation for t ≤ ⌊ Δ + 1 2 ⌋. We also show that a planar graph of maximum degree 3 having n vertices and m edges has a 2-unit bar visibility representation on 2 n − m columns and a 3-connected cubic graph of n vertices admits a 2-unit bar visibility representation on n 2 columns. [ABSTRACT FROM AUTHOR]