Geodesic
Drawing Recurrent Hierarchies
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 151-198.

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

Directed graphs are generally drawn as level drawings using the hierarchical approach. Such drawings are constructed by a framework of algorithms which operates in four phases: cycle removal, leveling, crossing reduction, and coordinate assignment. However, there are situations where cycles should be displayed as such, e. g., distinguished cycles in the biosciences and scheduling processes repeating in a daily or weekly turn. In their seminal paper on hierarchical drawings Sugiyama et al. [] also introduced recurrent hierarchies. This concept supports the drawing of cycles and their unidirectional display. However, it had not been investigated. In this paper we complete the cyclic approach and investigate the coordinate assignment phase. The leveling and the crossing reduction for recurrent hierarchies have been studied in the companion papers [,]. We provide an algorithm which runs in linear time and constructs an intermediate drawing with at most two bends per edge and aligned edge segments in an area of quadratic width times the preset number of levels height. This area bound is optimal for such drawings. Our approach needs new techniques for solving cyclic dependencies, such as skewing edges and cutting components. The drawings can be transformed into 2D drawings displaying all cycles counterclockwise around a center and into 3D drawings winding the cycles around a cylinder.
DOI : 10.7155/jgaa.00254
Keywords: recurrent hierarchies, Sugiyama framework, cyclic level graphs, coordinate assignment 
@article{JGAA_2012_16_2_a1,
     author = {Christian Bachmaier and Franz Brandenburg and Wolfgang Brunner and Raymund F\"ul\"op},
     title = {Drawing {Recurrent} {Hierarchies}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {151--198},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00254},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00254/}
}
TY  - JOUR
AU  - Christian Bachmaier
AU  - Franz Brandenburg
AU  - Wolfgang Brunner
AU  - Raymund Fülöp
TI  - Drawing Recurrent Hierarchies
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 151
EP  - 198
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00254/
DO  - 10.7155/jgaa.00254
LA  - en
ID  - JGAA_2012_16_2_a1
ER  - 
%0 Journal Article
%A Christian Bachmaier
%A Franz Brandenburg
%A Wolfgang Brunner
%A Raymund Fülöp
%T Drawing Recurrent Hierarchies
%J Journal of Graph Algorithms and Applications
%D 2012
%P 151-198
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00254/
%R 10.7155/jgaa.00254
%G en
%F JGAA_2012_16_2_a1
Christian Bachmaier; Franz Brandenburg; Wolfgang Brunner; Raymund Fülöp. Drawing Recurrent Hierarchies. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 151-198. doi : 10.7155/jgaa.00254. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00254/

Cité par Sources :