Bend-optimal orthogonal drawings of triconnected plane graphs

A drawing of a plane graph G in which each edge is represented by a sequence of alternating horizontal and vertical line segments is called an orthogonal drawing. The points of intersection of horizontal and vertical line segments of an edge in an orthogonal drawing are called bends. The best known algorithm to find a bend-optimal orthogonal drawing of a plane graph takes time O(n1.5) where n is the number of vertices in the graph. In this paper we present a new linear time algorithm to find an orthogonal drawing of a plane 3-connected graph (with maximum degree 4) and give bounds on number of bends (in terms of number k of degree-4 vertices in the graph) in the resulting drawing with respect to the number b(G) of bends in the bend-optimal orthogonal drawing of the same graph. The bound is b(G)+3k.