Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00436
On the Total Number of Bends for Planar Octilinear Drawings
Vol. 21, no. 4, pp. 709-730, 2017. Regular paper.
Abstract An octilinear drawing of a planar graph is one in which each
edge is drawn as a sequence of horizontal, vertical and diagonal at
$45^\circ$ and $-45^\circ$ line-segments. For such drawings to be
readable, special care is needed in order to keep the number of bends
small. Since the problem of finding planar octilinear drawings with
minimum number of bends is NP-hard, in this paper we focus on upper
and lower bounds. From a recent result of Keszegh et al. on the
slope number of planar graphs, we can derive an upper bound of
$4n-10$ bends for planar graphs with $n$ vertices and maximum
degree $8$. We considerably improve this general bound and
corresponding previous ones for triconnected planar graphs of maximum
degree $4$, $5$ and $6$. We also derive non-trivial lower bounds for
these three classes of graphs by a technique inspired by the network
flow formulation of Tamassia for computing bend optimal orthogonal
drawings.
|
Submitted: January 2016.
Reviewed: July 2016.
Revised: August 2016.
Reviewed: March 2017.
Revised: May 2017.
Accepted: June 2017.
Final: June 2017.
Published: June 2017.
Communicated by
Henk Meijer
|
Journal Supporters
|