A Linear Algorithm for Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs

An orthogonal drawing of a plane graph G is a drawing of G in which each edge is drawn as a sequence of alternate horizontal and vertical line segments. In this paper we give a linear-time algorithm to find an orthogonal drawing of a given 3-connected cubic plane graph with the minimum number of bends. The best known algorithm takes time O(n^{7/4} \sqrt {log n}) for any plane graph of n vertices