Intersection-Link Representations of Graphs

Angelini, Patrizio and Da Lozzo, Giordano and Di Battista, Giuseppe and Frati, Fabrizio and Patrignani, Maurizio and Rutter, Ignaz (2015) Intersection-Link Representations of Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 217-230 (Official URL:

Full text not available from this repository.


We consider drawings of graphs that contain dense subgraphs. We introduce intersection-link representations for such graphs, in which each vertex u is represented by a geometric object R(u) and in which each edge (u, v) is represented by the intersection between R(u) and R(v) if it belongs to a dense subgraph or by a curve connecting the boundaries of R(u) and R(v) otherwise. We study a notion of planarity, called Clique Planarity, for intersection-link representations of graphs in which the dense subgraphs are cliques.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.560 Geometry
P Styles > P.540 Planar
P Styles > P.999 Others
Z Theory > Z.500 Representations
ID Code:1491

Repository Staff Only: item control page


Angelin, P., Di Battista, G., Frati, F., Jelinek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. ACM Trans. Algorithms 11(4), 32:1–32:42 (2015). doi:10.​1145/​2629341

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Patrignani, M., Rutter, I.: Intersection-link representations of graphs. CoRR abs/1508.07557 (2015). http://​arxiv.​org/​abs/​1508.​07557

Angelini, P., Da Lozzo, G., Di Battista, G., Frati, F., Roselli, V.: The importance of being proper (in clustered-level planarity and T-level planarity). Theor. Comp. Sci. 571, 1–9 (2015)

Batagelj, V., Brandenburg, F., Didimo, W., Liotta, G., Palladino, P., Patrignani, M.: Visual analysis of large graphs using (x, y)-clustering and hybrid visualizations. IEEE Trans. Vis. Comput. Graph. 17(11), 1587–1598 (2011)

Bläsius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. In: Khanna, S. (ed.) SODA 2013, pp. 1030–1043. SIAM (2013)

Brandes, U., Raab, J., Wagner, D.: Exploratory network visualization: Simultaneous display of actor status and connections. J. Soc. Struct. 2 (2001)

Breu, H.: Algorithmic Aspects of Constrained Unit Disk Graphs. Ph.D. thesis, The University of British Columbia, Canada (1996)

Chen, Z., Grigni, M., Papadimitriou, C.H.: Map graphs. J. ACM 49(2), 127–138 (2002)

Cortese, P.F., Di Battista, G., Frati, F., Patrignani, M., Pizzonia, M.: C-planarity of c-connected clustered graphs. J. Graph Algorithms Appl. 12(2), 225–262 (2008)

Feng, Q.-W., Cohen, R.F., Eades, P.: Planarity for clustered graphs. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol. 979, pp. 213–226. Springer, Heidelberg (1995)

Heer, J., Boyd, D.: Vizster: Visualizing online social networks. In: Stasko, J.T., Ward, M.O. (eds.) InfoVis 2005, 23–25 October 2005, Minneapolis, USA, p. 5. IEEE Computer Society (2005)

Henry, N., Fekete, J., McGuffin, M.J.: Nodetrix: a hybrid visualization of social networks. IEEE Trans. Vis. Comput. Graph. 13(6), 1302–1309 (2007)

Hong, S.-H., Nagamochi, H.: Simpler algorithms for testing two-page book embedding of partitioned graphs. In: Cai, Z., Zelikovsky, A., Bourgeois, A. (eds.) COCOON 2014. LNCS, vol. 8591, pp. 477–488. Springer, Heidelberg (2014)

Irzhavsky, P.: Information System on Graph Classes and their Inclusions (ISGCI). http://​graphclasses.​org/​classes/​refs1600.​html#ref_​1660

Thorup, M.: Map graphs in polynomial time. In: FOCS 1998, pp. 396–405. IEEE (1998)

Wigderson, A.: The complexity of the Hamiltonian circuit problem for maximal planar graphs. EECS Department Report 298, Princeton University (1982)