Logo

Login | Create Account

Drawing Directed Graphs Using One-Dimensional Optimization

Carmel, Liran and Harel, David and Koren, Yehuda (2002) Drawing Directed Graphs Using One-Dimensional Optimization. [Conference Paper]

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
Classifications:M Methods > M.999 Others
M Methods > M.500 Layered
G Algorithms and Complexity > G.999 Others
ID Code:300
Deposited By:Martinez Leon, Victoria
Deposited On:07 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2528&spage=193

Repository Staff Only: item control page

References

1. 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.

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

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

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

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

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

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

8. 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.

9. 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.

10. 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.

11. 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.

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.