Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Slanted Orthogonal Drawings: Model, Algorithms and Evaluations
Michael A. Bekos, Michael Kaufmann, Robert Krug, Thorsten Ludwig, Stefan Näher, and Vincenzo Roselli
Vol. 18, no. 3, pp. 459-489, 2014. Regular paper.
Abstract We introduce a new model in the context of non-planar orthogonal graph drawing that we call slanted orthogonal graph drawing. While in traditional orthogonal drawings each edge is made of alternating axis-aligned line segments, in slanted orthogonal drawings intermediate diagonal segments on the edges are permitted, which allows for: (a) smoothening the bends of the produced drawing (as they are replaced by pairs of "half-bends"), and, (b) emphasizing the crossings of the drawing (as they always appear at the intersection of two diagonal segments). We present an approach to compute bend-optimal slanted orthogonal representations, an efficient heuristic to compute close-to-optimal slanted orthogonal drawings with respect to the total number of bends in quadratic area, and a corresponding LP formulation, when insisting on bend-optimality. On the negative side, we show that bend-optimal slanted orthogonal drawings may require exponential area.
Submitted: December 2013.
Reviewed: August 2014.
Revised: September 2014.
Accepted: November 2014.
Final: November 2014.
Published: November 2014.
Communicated by Giuseppe Liotta