At most single-bend embeddings of cubic graphs

This paper provides the complete proof of the fact that any planar cubic graph is at most single-bend embeddable except for the tetrahedron. An O(n) amortized time algorithm for drawing an at most single-bend embedding of a cubic graph is also presented, where n is the number of vertices of the graph. Furthermore, it is proved that the minimum of the total number of bends in an at most single-bend embedding of a cubic graph of order n is less than or equal to 0.5 n+1. This result is the best possible. © 1994 Editorial Committee of Applied Mathematics-A Journal of Chinese Universities.