  A planar orthogonal drawing $\Gamma$ of a planar graph $G$ is a geometric
representation of $G$ such that the vertices are drawn as distinct points of
the plane, the edges are drawn as chains of horizontal and vertical segments,
and no two edges intersect except at their common end-points. A bend of
$\Gamma$ is a point of an edge where a horizontal and a vertical segment meet.
$\Gamma$ is bend-minimum if it has the minimum number of bends over all
possible planar orthogonal drawings of $G$. This paper addresses a long
standing, widely studied, open question: Given a planar 3-graph $G$ (i.e., a
planar graph with vertex degree at most three), what is the best computational
upper bound to compute a bend-minimum planar orthogonal drawing of $G$ in the
variable embedding setting? In this setting the algorithm can choose among the
exponentially many planar embeddings of $G$ the one that leads to an orthogonal
drawing with the minimum number of bends. We answer the question by describing
an $O(n)$-time algorithm that computes a bend-minimum planar orthogonal drawing
of $G$ with at most one bend per edge, where $n$ is the number of vertices of
$G$. The existence of an orthogonal drawing algorithm that simultaneously
minimizes the total number of bends and the number of bends per edge was
previously unknown.
