Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00254
Drawing Recurrent Hierarchies
Vol. 16, no. 2, pp. 151-198, 2012. Regular paper.
Abstract
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.
|
Submitted: October 2010.
Reviewed: March 2011.
Revised: May 2011.
Accepted: December 2011.
Final: January 2012.
Published: January 2012.
Communicated by
Michael Kaufmann
|
Journal Supporters
|