Geodesic
Ideal Drawings of Rooted Trees With Approximately Optimal Width
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 631-648.

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

For rooted trees, an ideal drawing is one that is planar, straight-line, strictly-upward, and order-preserving. This paper considers ideal drawings of rooted trees with the objective of keeping the width of such drawings small. It is not known whether finding the minimum width is NP-hard or polynomial. This paper gives a 2-approximation for this problem, and a $2\Delta$-approximation (for $\Delta$-ary trees) where additionally the height is $O(n)$. For trees with $\Delta\leq 3$, the former algorithm finds ideal drawings with minimum width.
DOI : 10.7155/jgaa.00432
Keywords: graph drawing, rooted tree, upward drawing, order-preserving, approximation algorithm 
@article{JGAA_2017_21_4_a10,
     author = {Therese Biedl},
     title = {Ideal {Drawings} of {Rooted} {Trees} {With} {Approximately} {Optimal} {Width}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {631--648},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2017},
     doi = {10.7155/jgaa.00432},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00432/}
}
TY  - JOUR
AU  - Therese Biedl
TI  - Ideal Drawings of Rooted Trees With Approximately Optimal Width
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 631
EP  - 648
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00432/
DO  - 10.7155/jgaa.00432
LA  - en
ID  - JGAA_2017_21_4_a10
ER  - 
%0 Journal Article
%A Therese Biedl
%T Ideal Drawings of Rooted Trees With Approximately Optimal Width
%J Journal of Graph Algorithms and Applications
%D 2017
%P 631-648
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00432/
%R 10.7155/jgaa.00432
%G en
%F JGAA_2017_21_4_a10
Therese Biedl. Ideal Drawings of Rooted Trees With Approximately Optimal Width. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 631-648. doi : 10.7155/jgaa.00432. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00432/

Cité par Sources :