Drawing Directed Graphs Using One-Dimensional Optimization

Carmel, Liran and Harel, David and Koren, Yehuda (2002) Drawing Directed Graphs Using One-Dimensional Optimization. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 193-206 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_19).

Full text not available from this repository.

Abstract

We present an algorithm for drawing directed graphs, which is based on rapidly solving a unique one-dimensional optimization problem for each of the axes. The algorithm results in a clear description of the hierarchy structure of the graph. Nodes are not restricted to lie on fixed horizontal layers, resulting in layouts that convey the symmetries of the graph very naturally. The algorithm can be applied without change to cyclic or acyclic digraphs, and even to graphs containing both directed and undirected edges. We also derive a hierarchy index from the input digraph, which quantitatively measures its amount of hierarchy.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_19
Classifications:M Methods > M.999 Others
M Methods > M.500 Layered
G Algorithms and Complexity > G.999 Others
ID Code:300

Repository Staff Only: item control page

References

L. Carmel, D. Harel, Y. Koren, "Drawing Directed Graphs Using One-Dimensional Optimization", Technical Report MCS02-14, The Weizmann Institute of Science, 2001. Available on the web.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice-Hall, 1999.

J. Diaz, J. Petit and M. Serna, "A Survey on Graph Layout Problems", to appear in ACM Computing Surveys.

T.M.G. Fruchterman and E. Reingold, "Graph Drawing by Force-Directed Placement", Software Practice and Experience 21 (1991), 1129-1164.

K.M. Hall, "An r-dimensional Quadratic Placement Algorithm", Management Science 17 (1970), 219-229.

M. Kaufmann and D. Wagner (Eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, Vol. 2025, Springer Verlag, 2001.

Y. Koren, "On Spectral Graph Drawing", manuscript, 2002.

Y. Koren, L. Carmel and D. Harel, "ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs", Proc. IEEE Symp. on Information Visualization 2002 (InfoVis 2002), IEEE computer society press, to appear.

Y. Koren and D. Harel "A Multi-Scale Algorithm for the Linear Arrangement Problem", Proc. Graph Theoretical Concepts in Computer Science 2002 (WG 2002), Springer-Verlag, to appear.

K. Sugiyama and K. Misue, "A Simple and Unified Method for Drawing Graphs: Magnetic-Spring Algorithm", Proc. Graph Drawing 1994, Lecture Notes in Computer Science, Vol. 894, pp. 364-375, Springer Verlag, 1995.

K. Sugiyama, S. Tagawa and M. Toda, "Methods for Visual Understanding of Hierarchical Systems", IEEE Transactions on Systems, Man, and Cybernetics 11(2) (1981), 109-125.

W.T. Tutte, "How to draw a graph", Proc. London Math. Society 13 (1963), 743-768.