Geodesic
Upward planar drawings with two slopes
Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 1, pp. 171-198.

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

In an upward planar 2-slope drawing of a digraph, edges are drawn as straight-line segments in the upward direction without crossings using only two different slopes. We investigate whether a given upward planar digraph admits such a drawing and, if so, how to construct it. For the fixed embedding scenario, we give a simple characterisation and a linear-time construction by adopting algorithms from orthogonal drawings. For the variable embedding scenario, we describe a linear-time algorithm for single-source digraphs, a quartic-time algorithm for series-parallel digraphs, and a fixed-parameter tractable algorithm for general digraphs. For the latter two classes, we make use of SPQR-trees and the notion of upward spirality. As an application of this drawing style, we show how to draw an upward planar phylogenetic network with two slopes such that all leaves lie on a horizontal line.
DOI : 10.7155/jgaa.00587
Keywords: graph drawing, upward planar, upward spirality, slope number, phylogenetic network 
@article{JGAA_2022_26_1_a9,
     author = {Jonathan Klawitter and Tamara Mchedlidze},
     title = {Upward planar drawings with two slopes},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {171--198},
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2022},
     doi = {10.7155/jgaa.00587},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00587/}
}
TY  - JOUR
AU  - Jonathan Klawitter
AU  - Tamara Mchedlidze
TI  - Upward planar drawings with two slopes
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 171
EP  - 198
VL  - 26
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00587/
DO  - 10.7155/jgaa.00587
LA  - en
ID  - JGAA_2022_26_1_a9
ER  - 
%0 Journal Article
%A Jonathan Klawitter
%A Tamara Mchedlidze
%T Upward planar drawings with two slopes
%J Journal of Graph Algorithms and Applications
%D 2022
%P 171-198
%V 26
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00587/
%R 10.7155/jgaa.00587
%G en
%F JGAA_2022_26_1_a9
Jonathan Klawitter; Tamara Mchedlidze. Upward planar drawings with two slopes. Journal of Graph Algorithms and Applications, Tome 26 (2022) no. 1, pp. 171-198. doi : 10.7155/jgaa.00587. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00587/

Cité par Sources :