Algorithms for bar 1-visibility representations of graphs

Abstract

A bar visibility representation of a planar graph G is a drawing of G where each vertex is drawn as a horizontal line segment called bars, each edge is drawn as a vertical line segment where the vertical line segment representing an edge must connect the horizontal line segments representing the end vertices. A bar 1-visibility representation is a drawing of G where each vertex is drawn as a horizontal line segment, each edge is drawn as a vertical line segment where the vertical line segment representing an edge must connect the horizontal line segments representing the end vertices and a vertical line segment correspond- ing to an edge intersects at most one bar which is not an end point of the edge. A graph is a bar 1-visibility graph if it admits a bar 1-visibility represen- tation. A bar 1-visibility representation is a natural generalization of a visibility representation for a non-planar graph. However, complete characterizations of bar 1-visibility graphs are not known. In this thesis, we introduce “diagonal grid graphs” and “diagonal labeled graphs”, which are non-planar graphs, as bar 1-visibility graphs. We first give a linear-time algorithm for finding a bar 1-visibility representation of a diagonal grid graph. We then modify the algo- rithm for finding a visibility representation on a compact area. We also give an algorithm for finding a bar 1-visibility representation of a diagonal labeled graph in linear time.