Drawing Directed Graphs Clockwise

Pich, Christian (2010) Drawing Directed Graphs Clockwise. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 369-380 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_35).

Full text not available from this repository.

Abstract

We present a method for clockwise drawings of directed cyclic graphs. It is based on the eigenvalue decomposition of a skew-symmetric matrix associated with the graph and draws edges clockwise around the center instead of downwards, as in the traditional hierarchical drawing style. The method does not require preprocessing for cycle removal or layering, which often involves computationally hard problems. We describe an efficient algorithm which produces optimal solutions, and we present some application examples.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_35
Classifications:P Styles > P.999 Others
M Methods > M.500 Layered
ID Code:1099

Repository Staff Only: item control page

References

Bachmaier, C., Brandenburg, F.J., Brunner, W., Lovász, G.: Cyclic leveling of directed graphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 348–359. Springer, Heidelberg (2009)

Carmel, L., Harel, D., Koren, Y.: Combining hierarchy and energy for drawing directed graphs. IEEE Transactions on Visualization and Computer Graphics 10(1), 46–57 (2004)

Ganapathy, M.K., Lodha, S.P.: On minimum circular arrangement. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 394–405. Springer, Heidelberg (2004)

Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996)

Gower, J.C.: The analysis of asymmetry and orthogonality. In: Recent Developments in Statistics, pp. 109–123 (1977)

Gower, J.C., Constantine, A.G.: Graphical representation of asymmetric matrices. Applied Statistics 27, 297–304 (1978)

Harary, F., Moser, L.: The theory of round robin tournaments. Amer. Math. Monthly 73, 231–246 (1966)

Kaufmann, M., Wagner, D. (eds.): Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001)

Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. Journal of the ACM 46(5), 604–632 (1999)

Koren, Y.: On spectral graph drawing. In: Warnow, T.J., Zhu, B. (eds.) COCOON 2003. LNCS, vol. 2697, pp. 496–508. Springer, Heidelberg (2003)

Liberatore, V.: Circular arrangements and cyclic broadcast scheduling. Journal of Algorithms 51(2), 185–215 (2004)

Paardekooper, M.H.C.: An eigenvalue algorithm for skew-symmetric matrices. Numerische Mathematik 17(3), 189–202 (1971)

Reid, K.B., Beineke, L.W.: Tournaments. In: Beineke, L.W., Wilson, R.J. (eds.) Selected Topics in Graph Theory, pp. 169–204. Academic Press, London (1978)

Sugiyama, K., Misue, K.: A simple and unified method for drawing graphs: Magnetic-spring algorithm. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 364–375. Springer, Heidelberg (1995)

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics 11(2), 109–125 (1981)

Ward, R.C., Gray, L.C.: Ward and Leonard C. Gray. Eigensystem compuation for skew-symmetric matrices and a class of symmetric matrices. ACM Transactions on Mathematical Software 4(3), 278–285 (1978)