Geodesic
Minimum-Layer Upward Drawings of Trees
Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 245-267.

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

An upward drawing of a rooted tree T is a planar straight-line drawing of T where the vertices of T are placed on a set of horizontal lines, called layers, such that for each vertex u of T, no child of u is placed on a layer vertically above the layer on which u has been placed. In this paper we give a linear-time algorithm to obtain an upward drawing of a given rooted tree T on the minimum number of layers. Moreover, if the given tree T is not rooted, we can select a vertex r of T in linear time such that an upward drawing of T rooted at r would require the minimum number of layers among all the upward drawings of T with any of its vertices as the root. We also extend our results on a rooted tree to give an algorithm for an upward drawing of a rooted ordered tree. To the best of our knowledge, there is no previous algorithm for obtaining an upward drawing of a tree on the minimum number of layers.
DOI : 10.7155/jgaa.00206
Keywords: graph drawing, upward drawing, minimum-layer upward drawing, line-labeling, tree, algorithm 
@article{JGAA_2010_14_2_a5,
     author = {Muhammad Jawaherul Alam and Md. Abul Hassan Samee and Mashfiqui Rabbi and Md. Saidur Rahman},
     title = {Minimum-Layer {Upward} {Drawings} of {Trees}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {245--267},
     publisher = {mathdoc},
     volume = {14},
     number = {2},
     year = {2010},
     doi = {10.7155/jgaa.00206},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00206/}
}
TY  - JOUR
AU  - Muhammad Jawaherul Alam
AU  - Md. Abul Hassan Samee
AU  - Mashfiqui Rabbi
AU  - Md. Saidur Rahman
TI  - Minimum-Layer Upward Drawings of Trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2010
SP  - 245
EP  - 267
VL  - 14
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00206/
DO  - 10.7155/jgaa.00206
LA  - en
ID  - JGAA_2010_14_2_a5
ER  - 
%0 Journal Article
%A Muhammad Jawaherul Alam
%A Md. Abul Hassan Samee
%A Mashfiqui Rabbi
%A Md. Saidur Rahman
%T Minimum-Layer Upward Drawings of Trees
%J Journal of Graph Algorithms and Applications
%D 2010
%P 245-267
%V 14
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00206/
%R 10.7155/jgaa.00206
%G en
%F JGAA_2010_14_2_a5
Muhammad Jawaherul Alam; Md. Abul Hassan Samee; Mashfiqui Rabbi; Md. Saidur Rahman. Minimum-Layer Upward Drawings of Trees. Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 245-267. doi : 10.7155/jgaa.00206. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00206/

Cité par Sources :