Geodesic
Order-preserving Drawings of Trees with Approximately Optimal Height (and Small Width)
Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 1, pp. 1-19.

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

In this paper, we study how to draw trees so that they are planar, straight-line and respect a given order of edges around each node. We focus on minimizing the height, and show that we can always achieve a height of at most $2pw(T)+1$, where $pw(T)$ (the so-called pathwidth) is a known lower bound on the height of the tree $T$. Hence our algorithm provides an asymptotic 2-approximation to the optimal height. The width of such a drawing may not be a polynomial in the number of nodes. Therefore we give a second way of creating drawings where the height is at most $3pw(T)$, and where the width can be bounded by the number of nodes. Finally we construct trees $T$ that require height $2pw(T)+1$ in all planar order-preserving straight-line drawings. 
@article{JGAA_2020_24_1_a0,
     author = {Johannes Batzill and Therese Biedl},
     title = {Order-preserving {Drawings} of {Trees} with {Approximately} {Optimal} {Height} (and {Small} {Width)}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {1--19},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2020},
     doi = {10.7155/jgaa.00515},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00515/}
}
TY  - JOUR
AU  - Johannes Batzill
AU  - Therese Biedl
TI  - Order-preserving Drawings of Trees with Approximately Optimal Height (and Small Width)
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 1
EP  - 19
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00515/
DO  - 10.7155/jgaa.00515
LA  - en
ID  - JGAA_2020_24_1_a0
ER  - 
%0 Journal Article
%A Johannes Batzill
%A Therese Biedl
%T Order-preserving Drawings of Trees with Approximately Optimal Height (and Small Width)
%J Journal of Graph Algorithms and Applications
%D 2020
%P 1-19
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00515/
%R 10.7155/jgaa.00515
%G en
%F JGAA_2020_24_1_a0
Johannes Batzill; Therese Biedl. Order-preserving Drawings of Trees with Approximately Optimal Height (and Small Width). Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 1, pp. 1-19. doi : 10.7155/jgaa.00515. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00515/

Cité par Sources :