Orthogonal Drawings of Plane Graphs Without Bends - Rahman, Md. Saidur; Nishizeki, Takao; Naznin, Mahmuda (Journal of Graph Algorithms and Applications, 2003)
In an orthogonal drawing of a plane graph each vertexis drawn as a point and each edge is drawn as a sequence ofvertical and horizontal line segments. A bend is a point at whichthe drawing of an edge changes its direction.Every plane graph of the maximum degree at most four has an orthogonaldrawing, but may need bends.A simple necessary and sufficientcondition has not been known for a plane graph to have an orthogonaldrawing without bends. In this paper we obtain a necessaryand sufficient condition for a plane graph G of the maximumdegree three to have an orthogonal drawing without bends.We also give a linear-time algorithm to findsuch a drawing of G if it exists. <!---->