Improved circular layouts

Gansner, Emden R. and Koren, Yehuda (2007) Improved circular layouts. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 386-398 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_37).

Full text not available from this repository.

Abstract

Circular graph layout is a drawing scheme where all nodes are placed on the perimeter of a circle. An inherent issue with circular layouts is that the rigid restriction on node placement often gives rise to long edges and an overall dense drawing. We suggest here three independent, complementary techniques for lowering the density and improving the readability of circular layouts. First, a new algorithm is given for placing thenodes on the circle such that edge lengths are reduced. Second, we enhance the circular drawing style by allowing some of the edges to be routed around the exterior of the circle. This is accomplished with an algorithm for optimally selecting such a set of externally routed edges. The third technique reduces density by coupling groups of edges as bundled splines that share part of their route. Together, these techniques are able to reduce clutter, density and crossings compared with existing methods.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_37
Classifications:P Styles > P.120 Circular
ID Code:794

Repository Staff Only: item control page

References

M. Baur and U. Brandes, Crossing Reduction in Circular Layouts, Proc. Graph-Theoretic Concepts in Computer-Science (WG '04), 332-343, 2004.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari and F. Vargiu, An Experimental Comparison of Four Graph Drawing Algorithms, Comput. Geom. Theory Appl. 7, 303-325, 1997.

M. Dickerson, D. Eppstein, M. T. Goodrich and J. Meng, Confluent drawings: Visualizing Non-Planar Diagrams in a Planar Way, Proc. Graph Drawing (GD'03), 1-12, 2003.

4. U. Dogrusöz, B. Madden and P. Madden, Circular layout in the Graph Layout Toolkit, Proc. Graph Drawing (GD 96), 92-100, 2003, 1996

D. Eppstein, Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs, Journal of Experimental Algorithmics 5, 1-23, 2000.

M. K. Ganapathy and S. Lodha, On Minimum Circular Arrangement, Proc. 21st Annual Symposium on Theoretical Computer Science (STACS'04), 394-405, 2004.

E. R. Gansner, Y. Koren and S. North, Graph Drawing by StressMajorization, Proc. Graph Drawing (GD'04), 239-250, 2004.

E. R. Gansner and S. North, An Open Graph Visualization system and its Applications to Software Engineering, Software - Practice Experience 30, 1203-1233, 2000. Also, www.graphviz.org.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP Completeness, Freeman, 1979.

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

D. Holten and J. J. van Wijk, Hierarchical Edge Bundles: Visualization of Adjacency Relations in Hierarchical Data, Proc. IEEE Information Visualization (InfoVis'06), to appear.

G. Kar, B. Madden and R. S. Gilbert, Heuristic Layout Algorithms for Network Management Presentation Services, IEEE Network 29-36, 1988.

M. Kaufmann and R. Wiese, Maintaining the Mental Map for Circular Drawings, Proc. Graph Drawing (GD'02), 12-22, 2002.

V. Liberatore, Multicast Scheduling for List Requests, Proc. IEEE INFOCOM2002, 1129-1137, 2002.

S. Masuda, T. Kashiwabara, K. Nakajima and T. Fujisawa, On the NP-Completeness of a Computer Network Layout Problem, Proc. IEEE International Symposium on Circuits and Systems, 292-295, 1987.

F. J. Newbery, Edge Concentration: A Method for Clustering Directed Graphs, Proc. 2nd Intl. Workshop Software Configuration Management, 76-85, 1989.

J. M. Six and I. G. Tollis, Circular Drawings of Biconnected Graphs, Proc. Algorithms Engineering and Experimentation (ALENEX'99), 57-73, 1999.

J. M. Six and I. G. Tollis, A Framework for Circular Drawings of Networks, Proc. Graph Drawing (GD'99), 107-116, 1999.

K. Sugiyama, S. Tagawa and M. Toda, Methods for Visual Understanding of Hierarchical Systems, IEEE Trans. Systems, Man, and Cybernetics 11, 109-125, 1981.

A. Symeonidis and I. G. Tollis, Visualization of Biological Information with Circular Drawings, Proc. Biological and Medical Data Analysis (ISBMDA'04), 468-478, 2004.

W. T. Tutte, How to Draw a Graph, Proc. London Mathematical Society 13, 743-768, 1963.