Drawing Recurrent Hierarchies - Bachmaier, Christian; Brandenburg, Franz; Brunner, Wolfgang; Fülöp, Raymund (Journal of Graph Algorithms and Applications, 2012)
<!----> Directed graphs are generally drawn as level drawings using thehierarchical approach. Such drawings are constructed by a framework ofalgorithms 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 processesrepeating in a daily or weekly turn. <!----> In their seminal paper on hierarchical drawings Sugiyama et al.[] also introduced recurrent hierarchies. This conceptsupports the drawing of cycles and their unidirectional display. However,it had not been investigated. <!----> In this paper we complete the cyclic approach and investigate thecoordinate assignment phase. The leveling and the crossing reduction forrecurrent hierarchies have been studied in the companion papers[,]. <!----> We provide an algorithm which runs in linear time and constructs anintermediate drawing with at most two bends per edge and aligned edgesegments in an area of quadratic width times the preset number of levelsheight. This area bound is optimal for such drawings. Our approach needsnew techniques for solving cyclic dependencies, such as skewing edges andcutting components. The drawings can be transformed into 2D drawingsdisplaying all cycles counterclockwise around a center and into 3Ddrawings winding the cycles around a cylinder. <!---->