On the Total Number of Bends for Planar Octilinear Drawings - Bekos, Michael; Kaufmann, Michael; Krug, Robert (Journal of Graph Algorithms and Applications, 2017)
An octilinear drawing of a planar graph is one in which eachedge is drawn as a sequence of horizontal, vertical and diagonal at$45^°$ and $-45^°$ line-segments. For such drawings to bereadable, special care is needed in order to keep the number of bendssmall. Since the problem of finding planar octilinear drawings withminimum number of bends is NP-hard, in this paper we focus on upperand lower bounds. From a recent result of Keszegh et al. on theslope number of planar graphs, we can derive an upper bound of$4n-10$ bends for planar graphs with $n$ vertices and maximumdegree $8$. We considerably improve this general bound andcorresponding previous ones for triconnected planar graphs of maximumdegree $4$, $5$ and $6$. We also derive non-trivial lower bounds forthese three classes of graphs by a technique inspired by the networkflow formulation of Tamassia for computing bend optimal orthogonaldrawings.