Geodesic
On the Total Number of Bends for Planar Octilinear Drawings
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 709-730.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2017_21_4_a14,
     author = {Michael Bekos and Michael Kaufmann and Robert Krug},
     title = {On the {Total} {Number} of {Bends} for {Planar} {Octilinear} {Drawings}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {709--730},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2017},
     doi = {10.7155/jgaa.00436},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00436/}
}
TY  - JOUR
AU  - Michael Bekos
AU  - Michael Kaufmann
AU  - Robert Krug
TI  - On the Total Number of Bends for Planar Octilinear Drawings
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 709
EP  - 730
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00436/
DO  - 10.7155/jgaa.00436
LA  - en
ID  - JGAA_2017_21_4_a14
ER  - 
%0 Journal Article
%A Michael Bekos
%A Michael Kaufmann
%A Robert Krug
%T On the Total Number of Bends for Planar Octilinear Drawings
%J Journal of Graph Algorithms and Applications
%D 2017
%P 709-730
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00436/
%R 10.7155/jgaa.00436
%G en
%F JGAA_2017_21_4_a14
Michael Bekos; Michael Kaufmann; Robert Krug. On the Total Number of Bends for Planar Octilinear Drawings. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 709-730. doi : 10.7155/jgaa.00436. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00436/

Cité par Sources :