Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00343
Bar 1Visibility 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. 721739, 2014. Regular paper.
Abstract A graph is called a strong (resp. weak) bar 1visibility 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 1visibility graphs and other nearly planar graph classes. In particular, we study their relation to 1planar graphs, which have a drawing with at most one crossing per edge; quasiplanar graphs, which have a drawing with no three mutually crossing edges; and the squares of planar 1flow networks, which are upward digraphs with in or outdegree at most one. Our main results are that 1planar graphs and the (undirected) squares of planar 1flow networks are weak bar 1visibility graphs and that these are quasiplanar 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
