Abstract:
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.
Fulltext:
PDF file (370 kB)