Abstract:
This thesis deals with orthogonal drawings of plane graphs. Orthogonal drawings
have numerous practical applications in different fields of science and technology. In an
orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is
drawn as a sequence of vertical and horizontal line segments. The point at which the
drawing of an edge changes its direction in an orthogonal drawing is called a bend.
Minimization of the number of bends in an orthogonal drawing is a challenging problem.
A plane graph may have an orthogonal drawing without any bend. But no necessary and
sufficient condition is known for a plane graph to have an orthogonal drawing without
bends. In this thesis we establish a necessary and sufficient condition for a plane graph of
degree at most three to have an orthogonal drawing without bends. We also give a lineartime
algorithm to obtain such a drawing of a graph, if it exists.
