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.
