1-bend orthogonal drawings of triconnected planar 4-graphs

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.