Bar 1-Visibility Graphs and their relation to other Nearly Planar Graphs
William Evans, Michael Kaufmann, William Lenhart, Tamara Mchedlidze, and Stephen Wismath
Vol. 18, no. 5, pp. 721-739, 2014. Regular paper.
Abstract A graph is called a strong (resp. weak) bar 1-visibility graph if its vertices can be represented as horizontal segments (bars) in the plane so that its edges are all (resp. a subset of) the pairs of vertices whose bars have a ε-thick vertical line connecting them that intersects at most one other bar. We explore the relation among weak (resp. strong) bar 1-visibility graphs and other nearly planar graph classes. In particular, we study their relation to 1-planar graphs, which have a drawing with at most one crossing per edge; quasi-planar graphs, which have a drawing with no three mutually crossing edges; and the squares of planar 1-flow networks, which are upward digraphs with in- or out-degree at most one. Our main results are that 1-planar graphs and the (undirected) squares of planar 1-flow networks are weak bar 1-visibility graphs and that these are quasi-planar graphs.
Submitted: November 2013.
Reviewed: September 2014.
Revised: November 2014.
Accepted: November 2014.
Final: December 2014.
Published: December 2014.
Communicated by Joseph S. B. Mitchell
article (PDF)