Abstract:
An orthogonal drawing of a planar graph is a drawing of the graph in which each
vertex is mapped to a point, each edge is drawn as a sequence of alternate horizontal and
vertical line segments, and any two edges do not cross except at their common end. In an
orthogonal drawing, a bend is a point at which the drawing of an edge changes its direction.
Every planar 4-graph i.e. a graph with vertices of the maximum degree at most four, has
an orthogonal drawing, but may need bends. If the bend per edge of an orthogonal
drawing is at most k,then we call the drawing a k-bend orthogonal drawing. It is already
known that every planar 4-graph except an octahedron has a 2-bend orthogonal drawing.
Moreover, it is an NP-complete problem to decide whether a given planar 4-graph has a
Q-bendorthogonal drawing or not. In this thesis we consider I-bend orthogonal drawings
for planar 4-graphs. But unfortunately not every planar 4-graph has a I-bend orthogonal
drawing. That is why it is also interesting to find which class of planar 4-graphs has 1-
bend orthogonal drawings. In this thesis we give a sufficient condition for a triconnected
planar 4-graph to have a I-bend orthogonal drawing. Furthermore, we give a lineartime
algorithm for finding I-bend orthogonal drawings of those graphs which satisfy the
sufficient condition.
