Orthogonal drawings of plane graphs

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.