Geodesic
Uniform graph layering
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 2 (2018), pp. 85-98 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In the article we study an algorithm for layering directed acyclic graphs. We propose a method for such layering of the vertices when the vertices of a path are placed on layers with approximately equal intervals. At first the described algorithm places on layers those vertices which are located on the longests paths of the graph. Then the algorithm places on the same layers remaining vertices going through the paths not yet embedded in the order from longer ones to shorter ones. In order to find long paths which are not yet embedded we use a modified method of searching for paths in acyclic graphs based on depth-first search and topological sorting. It is proved that time complexity of the described algorithm when working on a graph $G=(V,E)$ is $O(|V||E|)$. Computing experiments were performed which showed that for not very large graphs with relatively low density the running time of the algorithm is acceptable for practical use.
Keywords: graph embedding on plane, layer assignment of vertices, Sugiyama's algorithm, time complexity. 
@article{VTPMK_2018_2_a4,
     author = {B. N. Karlov and A. V. Naimushin},
     title = {Uniform graph layering},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {85--98},
     year = {2018},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2018_2_a4/}
}
TY  - JOUR
AU  - B. N. Karlov
AU  - A. V. Naimushin
TI  - Uniform graph layering
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2018
SP  - 85
EP  - 98
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2018_2_a4/
LA  - ru
ID  - VTPMK_2018_2_a4
ER  - 
%0 Journal Article
%A B. N. Karlov
%A A. V. Naimushin
%T Uniform graph layering
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2018
%P 85-98
%N 2
%U http://geodesic.mathdoc.fr/item/VTPMK_2018_2_a4/
%G ru
%F VTPMK_2018_2_a4
B. N. Karlov; A. V. Naimushin. Uniform graph layering. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 2 (2018), pp. 85-98. http://geodesic.mathdoc.fr/item/VTPMK_2018_2_a4/

[1] Cormen T., Leiserson C., Rivest R., Stein C., Introduction to Algorithms, 2nd ed., MIT Press and McGraw-Hill, 2001

[2] Harary R., Graph Theory, Addison-Wesley, Reading, MA, 1969

[3] Bastert O., Matuszewski C., “Layered drawings of digraphs”, Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, 2025, eds. M. Kaufmann, D. Wagner, Springer-Verlag, 2001, 87-120 | DOI

[4] Carpano M. J., “Automatic Display of Hierarchized Graphs for Computer-Aided Decision Analysis”, IEEE Transactions on Systems, Man, and Cybernetics, 10:11 (1980), 705-715 | DOI

[5] Coffman E. G., Graham R. L., “Optimal scheduling for two processor systems”, Acta Informatica, 1 (1972), 200-213 | DOI

[6] Eiglsperger M., Kaufmann M., Siebenhaller M., “An efficient implementation of Sugiyama's algorithm for layered graph drawing”, Journal of Graph Algorithms and Applications, 9:3 (2005), 305-325 | DOI

[7] Gansner E., Koutsofios E., North S., Vo K.-P., “A technique for drawing directed graphs”, IEEE Trans. Softw. Eng, 19:3 (1993), 214-230 | DOI

[8] Sander G., “Graph layout for applications in compiler construction”, Theoretical Computer Science, 217:2 (1999), 175-214 | DOI

[9] Sugiyama K., Tagawa S., Toda M., “Methods for visual understanding of hierarchical system structures”, IEEE Transactions on Systems, Man, and Cybernetics, 11:2 (1981), 109-125 | DOI

[10] Warfield J. N., “Crossing theory and hierarchy mapping”, IEEE Transactions on Systems, Man, and Cybernetics, 7:7 (1977), 505-523 | DOI