×

One-dimensional layout optimization, with applications to graph drawing by axis separation. (English) Zbl 1115.05062

Summary: We discuss a useful family of graph drawing algorithms, characterized by their ability to draw graphs in one dimension. We define the special requirements from such algorithms and show how several graph drawing techniques can be extended to handle this task. In particular, we suggest a novel optimization algorithm that facilitates using the Kamada and Kawai model [T. Kamada and S. Kawai, Inf. Process. Lett. 31, No. 1, 7–15 (1989; Zbl 0679.68128)] for producing one-dimensional layouts. The most important application of the algorithms seems to be in achieving graph drawing by axis separation, where each axis of the drawing addresses different aspects of aesthetics.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
90C35 Programming involving graphs or networks

Citations:

Zbl 0679.68128

Software:

JIGGLE; ARPACK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Beckman, Theory of spectral graph layout, Technical Report MSR-TR-94-04, Microsoft Research, 1994; B. Beckman, Theory of spectral graph layout, Technical Report MSR-TR-94-04, Microsoft Research, 1994
[2] Brandes, U.; Cornelsen, S., Visual ranking of link structures, J. Graph Algorithms Appl., 7, 181-201 (2003) · Zbl 1041.68067
[3] Bruss, I.; Frick, A., Fast interactive 3-D graph visualization, (Proc. 3rd Inter. Symposium on Graph Drawing (GD’95). Proc. 3rd Inter. Symposium on Graph Drawing (GD’95), Lecture Notes Comput. Sci., vol. 1027 (1996), Springer: Springer Berlin), 99-110
[4] Carmel, L.; Harel, D.; Koren, Y., Combining hierarchy and energy for drawing directed graphs, IEEE Trans. Vis. Comput. Graph., 10, 46-57 (2004)
[5] Carmel, L.; Koren, Y.; Harel, D., Visualizing and classifying odors using a similarity matrix, (Proc. 9th International Symposium on Olfaction and Electronic Nose (ISOEN’02), Aracne (2003)), 141-146
[6] Cohen, J. D., Drawing graphs to convey proximity: an incremental arrangement method, ACM Trans. Computer-Human Interact., 4, 197-229 (1997)
[7] Diaz, J.; Petit, J.; Serna, M., A survey on graph layout problems, ACM Comput. Surv., 34, 313-356 (2002)
[8] Di Battista, G.; Eades, P.; Tamassia, R.; Tollis, I. G., Graph Drawing: Algorithms for the Visualization of Graphs (1999), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1057.68653
[9] Eades, P., A heuristic for graph drawing, Congressus Numerantium, 42, 149-160 (1984)
[10] Everitt, B. S.; Dunn, G., Applied Multivariate Data Analysis (1991), Arnold · Zbl 0788.62001
[11] Fruchterman, T. M.G.; Reingold, E., Graph drawing by force-directed placement, Software-Practice Exp., 21, 1129-1164 (1991)
[12] Gajer, P.; Goodrich, M. T.; Kobourov, S. G., A multi-dimensional approach to force-directed layouts of large graphs, (Proc. 8th Inter. Symposium on Graph Drawing (GD’00). Proc. 8th Inter. Symposium on Graph Drawing (GD’00), Lecture Notes Comput. Sci., vol. 1984 (2000), Springer: Springer Berlin), 211-221 · Zbl 1043.68618
[13] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), Johns Hopkins University Press · Zbl 0865.65009
[14] Hall, K. M., An \(r\)-dimensional quadratic placement algorithm, Management Sci., 17, 219-229 (1970) · Zbl 0203.52503
[15] Harel, D.; Koren, Y., Graph drawing by high-dimensional embedding, (Proc. 10th Inter. Symposium on Graph Drawing (GD’02). Proc. 10th Inter. Symposium on Graph Drawing (GD’02), Lecture Notes Comput. Sci., vol. 2528 (2002), Springer: Springer Berlin), 207-219 · Zbl 1037.68589
[16] Juvan, M.; Mohar, B., Optimal linear labelings and eigenvalues of graphs, Discrete Appl. Math., 36, 153-168 (1992) · Zbl 0759.05087
[17] Kamada, T.; Kawai, S., An algorithm for drawing general undirected graphs, Inform. Process. Lett., 31, 7-15 (1989) · Zbl 0679.68128
[18] (Kaufmann, M.; Wagner, D., Drawing Graphs: Methods and Models. Drawing Graphs: Methods and Models, Lecture Notes Comput. Sci., vol. 2025 (2001), Springer: Springer Berlin) · Zbl 0977.68644
[19] Koren, Y.; Carmel, L.; Harel, D., Drawing huge graphs by algebraic multigrid optimization, Multiscale Modeling and Simulation, 1, 645-673 (2003) · Zbl 1041.65036
[20] Koren, Y.; Harel, D., A multi-scale algorithm for the linear arrangement problem, (Proc. 28th Inter. Workshop on Graph-Theoretic Concepts in Computer Science (WG’02). Proc. 28th Inter. Workshop on Graph-Theoretic Concepts in Computer Science (WG’02), Lecture Notes Comput. Sci., vol. 2573 (2002), Springer: Springer Berlin), 293-306
[21] Koren, Y.; Harel, D., A two-way visualization method for clustered data, (Proc. 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’03) (2003), ACM Press: ACM Press New York), 589-594
[22] Koren, Y.; Harel, D., Axis-by-axis stress minimization, (Proc. 11th Inter. Symposium on Graph Drawing (GD’03) (2003), Springer: Springer Berlin), 450-459 · Zbl 1215.05187
[23] Koren, Y., Graph drawing by subspace optimization, (Proc. 6th Eurographics—IEEE TCVG Symposia on Visualization (VisSym’04) (2004), Eurographics), 65-74
[24] Kruskal, J.; Seery, J., Designing network diagrams, (Proc. First General Conference on Social Graphics (1980), US Department of the Census), 22-50
[25] Lehoucq, B.; Sorensen, D. C.; Yang, C., ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods (1998), SIAM · Zbl 0901.65021
[26] A.J. McAllister, A new heuristic algorithm for the linear arrangement problem, Technical Report 99_126a, Faculty of Computer Science, University of New Brunswick, 1999; A.J. McAllister, A new heuristic algorithm for the linear arrangement problem, Technical Report 99_126a, Faculty of Computer Science, University of New Brunswick, 1999
[27] Mohar, B., The Laplacian spectrum of graphs, Graph Theory Combin. Appl., 2, 871-898 (1991) · Zbl 0840.05059
[28] Sugiyama, K.; Tagawa, S.; Toda, M., Methods for visual understanding of hierarchical systems, IEEE Trans. Systems Man Cybernet., 11, 109-125 (1981)
[29] Sammon, J. W., A nonlinear mapping for data structure analysis, IEEE Trans. Comput., 18, 401-409 (1969)
[30] D. Tunkelang, A numerical optimization approach to general graph drawing, Ph.D. Thesis, Carnegie Mellon University, 1999; D. Tunkelang, A numerical optimization approach to general graph drawing, Ph.D. Thesis, Carnegie Mellon University, 1999
[31] Walshaw, C., A multilevel algorithm for force-directed graph drawing, J. Graph Algorithms Appl., 7, 253-285 (2003) · Zbl 1068.68109
[32] The Matrix Market collection
[33] The University of Greenwich Graph Partitioning Archive
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.