Computing NodeTrix Representations of Clustered Graphs
NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and inter-cluster edges as curves connecting the matrix boundaries. We study the complexity of constructing NodeTrix representations fo
- PDF / 605,194 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 193 Views
Abstract. NodeTrix representations are a popular way to visualize clustered graphs; they represent clusters as adjacency matrices and intercluster edges as curves connecting the matrix boundaries. We study the complexity of constructing NodeTrix representations focusing on planarity testing problems, and we show several NP-completeness results and some polynomial-time algorithms.
1
Introduction and Overview
NodeTrix representations have been introduced by Henry et al. [17] in one of the most cited papers of the InfoVis conference [1]. A NodeTrix representation is a hybrid representation for the visualization of social networks where the node-link paradigm is used to visualize the overall structure of the network, within which adjacency matrices show communities. Formally, a NodeTrix (NT for short) representation is defined as follows. A flat clustered graph (V, E, C) is a graph (V, E) with a partition C of V into sets V1 , . . . , Vk , called clusters, that can be defined according to the application needs. The word “flat” is used to underline that clusters are not arranged in a multi-level hierarchy [10,13]. An edge (u, v) ∈ E with u ∈ Vi and v ∈ Vj is an intra-cluster edge if i = j and is an inter-cluster edge if i = j. In an NT representation clusters V1 , . . . , Vk are represented by non-overlapping symmetric adjacency matrices M1 , . . . , Mk , where Mi is drawn in the plane so that its boundary is a square Qi with sides parallel to the coordinate axes. Thus, the matrices M1 , . . . , Mk convey the information about the intra-cluster edges of (V, E, C), while each inter-cluster edge (u, v) with u ∈ Vi and v ∈ Vj is represented by a curve connecting a point on Qi with a point on Qj , where the point on Qi (on Qj ) belongs to the column or to the row of Mi (resp. of Mj ) associated with u (resp. with v). Several papers aimed at improving the readability of NT representations by reducing the number of crossings between inter-cluster edges. For this purpose, vertices can have duplicates in different matrices [16] or clusters can be computed so to have dense intra-cluster graphs and a planar inter-cluster graph [9]. Research partially supported by MIUR project AMANDA, prot. 2012C4E3KT 001. c Springer International Publishing AG 2016 Y. Hu and M. N¨ ollenburg (Eds.): GD 2016, LNCS 9801, pp. 107–120, 2016. DOI: 10.1007/978-3-319-50106-2 9
108
G. Da Lozzo et al.
In this paper we study the problem of automatically constructing an NT representation of a given flat clustered graph. This problem combines traditional graph drawing issues, like the placement of a set of geometric objects in the plane (here the squares Q1 , . . . , Qk ) and the routing of the graph edges (here the inter-cluster edges), with a novel algorithmic challenge: To handle the degrees of freedom given by the choice of the order for the rows and the columns of the matrices and by the choice of the side of the matrices to which the inter-cluster edges attach to. Indeed, the order of the rows and columns of a matrix Mi is arbitrary, as long as Mi
Data Loading...
