Visual Analysis of One-To-Many Matched Graphs

Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Palladino, Pietro (2009) Visual Analysis of One-To-Many Matched Graphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 133-144 (Official URL:

Full text not available from this repository.


Motivated by applications of social network analysis and of Web search clustering engines, we describe an algorithm and a system for the display and the visual analysis of two graphs G1 and G2 such that each Gi is defined on a different data set with its own primary relationships and there are secondary relationships between the vertices of G1 and those of G2 . Our main goal is to compute a drawing of G1 and G2 that makes clearly visible the relations between the two graphs by avoiding their crossings, and that also takes into account some other important aesthetic requirements like number of bends, area, and aspect ratio. Application examples and experiments on the system performances are also presented.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_14
Classifications:P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.180 Cluster
P Styles > P.120 Circular
M Methods > M.700 Planarization-based
ID Code:903

Repository Staff Only: item control page


GDToolkit: Graph drawing toolkit,∼gdt/IEEE Symposium on Information Visualization (InfoVis 2007), 28-30 October 2007, Sacramento, CA, USA. IEEE Computer Society (2007)

Hong, S.-H., Nishiuzeki, T., Quan, W. (eds.): GD 2007. LNCS, vol. 4875. Spirnger, Heidelberg (2008)

Intern. Symposium on Graph Drawing, (GD 2007), 24-26 September 2007, Sydney, Australia. Springer (2007)

IEEE VGTC Pacific Visualization Symposium 2008 (PacificVis 2008), 4-7 March, Kyoto, Japan, 2008. IEEE Computer Society (2008)

Baur, M., Brandes, U.: Crossing reduction in circular layouts. In: WG 2004. LNCS, vol. 3353, pp. 332–343 (2004)

Baur, M., Brandes, U.: Multi-circular layout of micro/macro graphs. In:GD 2007. LNCS, vol. 4875, pp. 255–267, Springer, Heidelberg (2008)

Braß, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. Comput. Geom.: Theory and Appl. 36(2), 117–130 (2007)

Collins, C., Carpendale, M.S.T.: Vislink: Revealing relationships amongst visualizations. IEEE Trans. Vis. Comput. Graph. 13(6), 1192–1199 (2007)

Di Battista, G., Didimo, W., Patrignani, M., Pizzonia, M.: Orthogonal and quasi-upward drawings with vertices of prescribed sizes. In: GD 1999. LNCS, vol. 1731, pp. 297–310 (1999)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall (1999)

Di Giacomo, E., Didimo, W., van Kreveld, M.J., Liotta, G., Speckmann, B.: Matched drawings of planar graphs. In: GD 2007. LNCS, vol. 4875, pp. 183–194, Springer, Heidelberg(2008)

Di Giacomo, E., Didimo, W., Palladino, P., Liotta, G.: Visual analysis of one-to-many matched graphs. Tech. rep. (2008), RT-003-08, DIEI - Universita di Perugia, Italy

Di Giacomo, E., Liotta, G.: Simultaneous embedding of outerplanar graphs, paths, and cycles. Intern. Journ. of Comput. Geom. and Appl. 17(2), 139–160 (2007)

Erten, C., Harding, P.J., Kobourov, S.G., Wampler, K., Yee, G.V.:Graphael: Graph animations with evolving layouts. In: GD 2003. LNCS, vol. 2912, pp. 98–110 (2004)

Erten, C., Kobourov, S.G.: Simultaneous embedding of a

planar graph and its dual on the grid. Theory Comput. Syst. 38(3), 313–327 (2005)

Erten, C., Kobourov, S.G., Le, V., Navabi, A.: Simultaneous graph drawing: Layout algorithms and visualization schemes. Journ. Graph Alg. and Appl. 9(1), 165–182 (2005)

Gutwenger, C., Klein, K., Mutzel, P.: Planarity testing and optimal edge insertion with embedding constraints. Journ. of Graph Alg. and Appl. 12(1), 73–95 (2008)

Masuda, S., Kashiwabara, T., Nakajima, K., Fujisawa, T.: On the NP-completeness of a computer network layout problem. In: 20th IEEE Int. Symposium on Circuits and Systems. pp. 292–295 (1987)

Shneiderman, B., Aris, A.: Network visualization by semantic substrates. IEEE Trans. Vis. Comput. Graph. 12(5), 733–740 (2006)

Six, J.M., Tollis, I.G.: A framework and algorithms for circular drawings of graphs. Journ. of Discr. Alg. 4(1), 25–50 (2006)