Computing NodeTrix Representations of Clustered Graphs

Abstract

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 focusing on planarity testing problems, and we show several $\mathbb {NP}$-completeness results and some polynomial-time algorithms.

Research partially supported by MIUR project AMANDA, prot. 2012C4E3KT_001.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

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,\mathcal {C})$ is a graph (V, E) with a partition $\mathcal {C}$ of V into sets $V_1,\dots ,V_k$, 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) \in E$ with $u \in V_i$ and $v \in V_j$ is an intra-cluster edge if $i=j$ and is an inter-cluster edge if $i\ne j$. In an NT representation clusters $V_1,\dots ,V_k$ are represented by non-overlapping symmetric adjacency matrices $M_1,\dots ,M_k$, where $M_i$ is drawn in the plane so that its boundary is a square $Q_i$ with sides parallel to the coordinate axes. Thus, the matrices $M_1,\dots ,M_k$ convey the information about the intra-cluster edges of $(V,E,\mathcal{C})$, while each inter-cluster edge (u, v) with $u \in V_i$ and $v \in V_j$ is represented by a curve connecting a point on $Q_i$ with a point on $Q_j$, where the point on $Q_i$ (on $Q_j$) belongs to the column or to the row of $M_i$ (resp. of $M_j$) 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].

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 $Q_1,\dots ,Q_k$) 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 $M_i$ is arbitrary, as long as $M_i$ is symmetric; further, an inter-cluster edge incident to $M_i$ can arbitrarily exit $M_i$ from four sides: left or right if it exits $M_i$ from its associated row, or top or bottom if it exits $M_i$ from its associated column.

When working on a new model for graph representations, the very first step is usually to study the complexity of testing if a graph admits a planar representation within that model. Hence, in Sect. 2 we deal with the problem of testing if a flat clustered graph admits a planar NT representation. An NT representation is planar if no inter-cluster edge e intersects any matrix $M_i$, except possibly at an end-point of e on $Q_i$, and no two inter-cluster edges e and $e'$ cross each other, except possibly at a common end-point. The NT Planarity problem asks if a flat clustered graph admits a planar NT representation.

Our findings show how tough the problem is (see Table 1). Namely, we show that NT Planarity is $\mathbb {NP}$-complete even if the order of the rows and of the columns of the matrices is fixed (i.e., it is part of the input), or if the exit sides of the inter-cluster edges are fixed. It is easy to show that NT Planarity becomes linear-time solvable if both the order and the sides are fixed. But this is probably too restrictive for practical applications since all the degrees of freedom that are representation-specific are lost.

Table 1. Complexity results for NT Planarity. The result marked $\dag$ assumes that the number of clusters is constant.

Motivated by such complexity results, in Sect. 3 we study a more constrained model that is still useful for practical applications. A monotone NT representation is an NT representation in which the matrices have prescribed positions and the inter-cluster edges are represented by xy-monotone curves inside the convex hull of their incident matrices. We require that this convex hull does not intersect any other matrix. We study this model for two reasons. First, in most of (although not in all) the available examples of NT representations the inter-cluster edges are represented by xy-monotone curves (see, e.g., NodeTrix clips and prototype [2]). Second, we are interested in supporting a visualization system where the position of the matrices is decided by the user and the inter-cluster edges are automatically drawn with “few” crossings. Therefore, the crossings between inter-cluster edges not incident to a common matrix are somehow unavoidable, as they depend on the positions of the matrices selected by the users, and we are only interested in reducing the number of local crossings, that are the crossings between pairs of edges incident to the same matrix.

We say that an NT representation is locally planar if no two inter-cluster edges incident to the same matrix cross. While testing if a flat clustered graph admits a monotone NT locally planar representation is $\mathbb {NP}$-complete even if the sides are fixed (see Table 1), the problem becomes polynomial-time solvable in the reasonable scenario in which the number of matrices is constant, the order of the rows and columns is fixed, and the sides of the matrices to which the inter-cluster edges attach is variable.

Conclusions and open problems are discussed in Sect. 4 where NT Planarity is related to graph drawing problems of theoretical interest.

Before proceeding to prove our results, we establish formal definitions and notation. An NT representation consists of: (a) A row-column order $\sigma _i$ for each cluster $V_i$, that is, a bijection $\sigma _i: V_i \leftrightarrow \{1,\dots ,|V_i|\}$. (b) A side assignment $s_i$ for each inter-cluster edge incident to $V_i$, that is, an injective mapping $s_i: \bigcup _{j\ne i}{E_{i,j}} \rightarrow \{\textsc {t}, {\textsc {b}}, {\textsc {l}}, {\textsc {r}}\}$, where $E_{i,j}$ is the set of inter-cluster edges between the clusters $V_i$ and $V_j$ ($V_i$ and $V_j$ are adjacent if $E_{i,j}\ne \emptyset$). (c) A matrix $M_i$ for each cluster $V_i$, that is, a representation of $V_i$ as a symmetric adjacency matrix such that: (i) the boundary of $M_i$ is a square $Q_i$ with sides parallel to the coordinate axes; let $\min _x(Q_i)$ be the minimum x-coordinate of a point on $Q_i$; $\min _y(Q_i)$, $\max _x(Q_i)$, and $\max _y(Q_i)$ are defined analogously; (ii) the left-to-right order of the columns and the top-to-bottom order of the rows in $M_i$ is $\sigma _i$; and (iii) every two distinct matrices are disjoint; if $V_i$ has only one vertex, we often talk about the matrix representing that vertex, rather than the matrix representing $V_i$. (d) An edge drawing for each inter-cluster edge $e=(u,v)$ with $u \in V_i$ and $v \in V_j$, that is, a representation of e as a Jordan curve between two points $p_u$ and $p_v$ defined as follows. Let $m^u_{\textsc {t}}$ be the mid-point of the line segment that is the intersection of the top side of $Q_i$ with the column associated to u in $M_i$; points $m^u_{\textsc {b}}$, $m^u_{\textsc {l}}$, and $m^u_{\textsc {r}}$ are defined analogously. Then $p_u$ coincides with $m^u_{\textsc {t}}$, $m^u_{\textsc {b}}$, $m^u_{\textsc {l}}$, or $m^u_{\textsc {r}}$ if $s_i(e)=\textsc {t}$, $s_i(e)=\textsc {b}$, $s_i(e)=\textsc {l}$, or $s_i(e)=\textsc {r}$, respectively. Point $p_v$ is defined analogously. The full versi on of the paper [12] contains complete proofs.

2 Testing NodeTrix Planarity

In this section we study the time complexity of testing NodeTrix Planarity.

Theorem 1

NodeTrix Planarity is $\mathbb {NP}$-complete even if at most three clusters contain more than one vertex.

Proof Sketch:

Lemma 1 will prove that NT Planarity is in $\mathbb {NP}$. For the $\mathbb {NP}$-hardness we give a reduction from the $\mathbb {NP}$-complete problem Partitioned 3-Page Book Embedding [7] that, given a graph $\langle V, E= E_1\cup E_2\cup E_3\rangle$, asks whether a total ordering $\mathcal O$ of V exists such that no two edges e and $e'$ in the same set $E_i$ have alternating end-vertices in $\mathcal O$. We construct an instance $\langle V',E',\mathcal {C}' \rangle$ of NT Planarity from $\langle V, E = E_1\cup E_2\cup E_3\rangle$ as follows; see Fig. 1.

The instance $\langle V',E',\mathcal {C}' \rangle$ has a cycle D composed of vertices $u_l$, $t^i_j$, $u_r$, $b^i_j$, and $u^i_b$, where $i=1,\dots ,3$ and $j=1,\dots ,7$ (each in a distinct cluster containing that vertex only) and of inter-cluster edges called bounding edges. The instance contains three “big” clusters $V''_i=V'_i \cup \{x_i,y_i,w_i,z_i\}$ with $i=1,2,3$, where $V'_i$ is in bijection with V; these are the only clusters with more than one vertex. Any two vertices, one in $V'_i$ and one in $V'_{i+1}$, that are in bijection (via a vertex in V) are connected by an order-preserving edge. Further, the vertices $x_i,y_i,w_i,z_i$ of $V''_i$ are connected to the vertices in D via corner edges, and side-filling edges connect $u_l$ with every vertex in $V'_1$, $u_r$ with every vertex in $V'_3$, and $u^i_b$ with every vertex in $V'_i$. Finally, $\langle V',E',\mathcal {C}' \rangle$ contains paths corresponding to the edges in E; namely, for every $e=(r,s)\in E_i$, $\langle V',E',\mathcal {C}' \rangle$ contains a cluster $\{u'_e\}$ and two equivalence edges $(u'_e,r'_i)$ and $(u'_e,s'_i)$, where $r'_i$ and $s'_i$ are the vertices in $V'_i$ in bijection with r and s, respectively. The construction can be easily performed in polynomial time. We now prove the equivalence between the two instances.

For the direction ($\Longrightarrow$), consider a total order $\mathcal O$ of V which solves instance $\langle V, E\rangle$. An order $\sigma '_i$ of $V'_i$ is constructed from $\mathcal O$ via the bijection between $V'_i$ and V; then define an order $\sigma _i$ of $V''_i$ as $x_i,y_i,\sigma '_i,w_i,z_i$. Embed D in the plane and embed each matrix $M_i$ representing $V''_i$ inside D with row-column order $\sigma _i$. The corner, order-preserving, and side-filling edges are routed inside D so that their end-vertices are not assigned to the top side of $M_i$; for example, the side-filling edges incident to $u_l$ (to $u^1_b$) are assigned to the left (resp. bottom) side of $M_1$ and the order-preserving edges incident to $V'_1$ are assigned to the right side of $M_1$; the order-preserving edges can be routed without crossings since $\sigma '_i$ and $\sigma '_{i+1}$ coincide (via the bijection of $V'_i$ and $V'_{i+1}$ with V). Finally, each path $(r'_i,u'_e,s'_i)$ corresponding to an edge $(r,s)\in E_i$ is incident to the top side of $M_i$; no two of these paths have alternating end-vertices since $\sigma '_i$ coincides with $\mathcal O$ (via the bijection between $V'_i$ and V) and since no two edges in $E_i$ have alternating end-vertices in $\mathcal O$. This results in a planar NT representation of $\langle V',E',\mathcal {C}' \rangle$.

The direction ($\Longleftarrow$) is more involved. Consider a planar NT representation $\varGamma$ of $\langle V',E',\mathcal {C}' \rangle$. First, the matrices representing clusters not in D induce a connected part of $\varGamma$, hence they are all on the same side of D, say they are all inside D. Second, the boundary $Q_i$ of $M_i$ and the corner edges incident to it subdivide the interior of D into five regions, namely one containing $M_i$, and four incident to the sides of $Q_i$. All the vertices in $V'_i$ are incident to each of the latter four regions; this is proved by arguing that the first two and the last two vertices in the row-column order $\sigma _i$ of $M_i$ are among $\{x_i,y_i,w_i,z_i\}$, and by arguing about how the corner edges are incident to the sides of $Q_i$. Third, the side-filling edges incident to a same vertex in D “fill” one of such regions and so do the order-preserving edges connecting $M_i$ with $M_{i+1}$ (or with $M_{i-1}$). Hence, all the equivalence edges are incident to the same side of $Q_i$. Finally, the order-preserving edges between vertices in $V'_i$ and in $V'_{i+1}$ are in the region shared by $M_i$ and $M_{i+1}$; these regions are gray in Fig. 1. This implies that $\sigma '_i$ and $\sigma '_{i+1}$ are either the same or the reverse of each other, via the bijection with the vertices in V. Hence, we define an order $\mathcal O$ of V according to the bijection with the order $\sigma '_i$ of $V'_i$; then no two edges in $E_1$, in $E_2$, or in $E_3$ have alternating end-vertices, as otherwise the corresponding paths would cross in $\varGamma$.    $\square$

Fig. 1.

(a) An instance $\langle V, E= E_1\cup E_2 \cup E_3\rangle$ of Partitioned 3-Page Book Embedding and (b) the corresponding instance $\langle V',E', \mathcal {C}' \rangle$ of NT Planarity.

Fig. 2.

Illustration for Theorem 2.

Let $G=(V,E,\mathcal {C})$ be a flat clustered graph with a given side assignment $s_i$, for each $V_i \in \mathcal {C}$. We say that G is NT planar with fixed side if G admits a NT planar representation $\varGamma$ such that, $\forall e=(u,v) \in E$ with $u \in V_i$ and $v \in V_j$, the incidence points of e with the matrices $M_i$ and $M_j$ representing $V_i$ and $V_j$ in $\varGamma$, respectively, lie on the segments corresponding to the $s_i(u)$ side of $M_i$ and to the $s_j(v)$ side of $M_j$, respectively.

Theorem 2

NodeTrix Planarity with Fixed Side is $\mathbb {NP}$-complete even for instances with two clusters.

Proof Sketch:

Lemma 1 will prove that NT Planarity with Fixed Side is in $\mathbb {NP}$. For the $\mathbb {NP}$-hardness we give a reduction from Betweenness [18], whose input is a set of items $\{a_1,\dots a_h\}$ and a collection of t ordered triples $\tau _j = \langle a_{b_j},a_{c_j},a_{d_j} \rangle$. The goal is to find a total order of the items such that, for each $\tau _j = \langle a_{b_j},a_{c_j},a_{d_j} \rangle$, item $a_{c_j}$ is between $a_{b_j}$ and $a_{d_j}$. We construct the corresponding instance of NT Planarity with Fixed Side by defining a flat clustered graph $(V,E,\mathcal {C} = \{V_1, V_2\})$ and side assignments $s_1$ and $s_2$ as follows; refer to Fig. 2. Cluster $V_1$ ($V_2$) contains t vertices for each $a_i$ plus two vertices $v_\alpha$ and $v_\beta$ (plus two vertices $u_\alpha$ and $u_\beta$ and 2t vertices $t_{j1}$ and $t_{j2}$ for $j=1,\dots ,t$). Let $M_1$ and $M_2$ be matrices representing $V_1$ and $V_2$, respectively; also, let $e_{\alpha }=(u_\alpha ,v_\alpha )$ ($e_{\beta }=(u_\beta ,v_\beta )$) be assigned to the right (left) side of $M_1$ and to the left (right) side of $M_2$. We associate to each element $a_i$ a $(2t+1)$-vertex path $\pi _i$ that starts at $u_{\beta }$, and repeatedly leaves the bottom side of $M_2$, enters the bottom side of $M_1$, leaves the top side of $M_1$, and enters the top side of $M_2$; this routing of $\pi _i$ can be prescribed by $s_1$ and $s_2$. Further, for every even j, the left-to-right order of the columns associated to the j-th vertices of paths $\pi _1,\dots ,\pi _h$ in $M_1$ is the same. This allows us to introduce five inter-cluster edges for each triple $\tau _j = \langle a_{b_j},a_{c_j},a_{d_j} \rangle$, all connecting the right side of $M_1$ with the left side of $M_2$. These edges connect the j-th vertex in $\pi _{b_j}$ to $t_{j1}$, the j-th vertex in $\pi _{c_j}$ to $t_{j1}$ and $t_{j2}$, and the j-th vertex in $\pi _{d_j}$ to $t_{j2}$. These five edges can be drawn without crossings if and only if the row associated to the j-th vertex in $\pi _{c_j}$ is between the rows associated to the j-th vertices in $\pi _{b_j}$ and $\pi _{d_j}$. This establishes the desired correspondence with the Betweenness problem.    $\square$

Let $G=(V,E,\mathcal {C})$ be a flat clustered graph with a given row-column order $\sigma _i$, for each $V_i \in \mathcal {C}$. We say that G is NT planar with fixed order if it admits a NT planar representation $\varGamma$ where, for each $V_i \in \mathcal {C}$, each vertex $v \in V_i$ is associated with the $\sigma _i(v)$-th row and column of the matrix $M_i$ representing $V_i$ in $\varGamma$.

Theorem 3

NodeTrix Planarity with Fixed Order is $\mathbb {NP}$-complete even if at most one cluster contains more than one vertex.

Fig. 3.

(a) An intersection representation $\langle \mathcal {P}, \mathcal {O} \rangle$ of a circle graph $G=(N,A)$. (b) Instance $(V,E,\mathcal {C})$ of NodeTrix Planarity corresponding to $\langle \mathcal {P}, \mathcal {O} \rangle$.eps

Proof Sketch:

The membership in $\mathbb {NP}$ will be proved in Lemma 1. For the $\mathbb {NP}$-hardness, we give a reduction from the 4-coloring problem for circle graphs [20]. We construct in polynomial time [19] a representation $\langle \mathcal {P}, \mathcal {O} \rangle$ of G, where $\mathcal {P}$ is a linear sequence of distinct points on a circle and $\mathcal {O}$ is a set of chords between points in $\mathcal {P}$ such that: (i) each chord $c \in \mathcal {O}$ corresponds to a vertex $n \in N$ and (ii) two chords $c',c''\in \mathcal {O}$ intersect if and only if $(n',n'') \in A$, where $n'$ and $n''$ are the vertices in N corresponding to $c'$ and $c''$, respectively. Starting from $\langle \mathcal {P}, \mathcal {O} \rangle$ we construct an instance $(V,E,\mathcal {C})$ of NodeTrix Planarity with Fixed Order as follows (refer to Fig. 3). The instance $(V,E,\mathcal {C})$ contains: (i) a cycle D composed of vertices $v_{tl}$, $v'_{tr}$, $v''_{tr}$, $v_{br}$, $v'_{bl}$, and $v''_{bl}$ (each in a distinct cluster containing that vertex only) and of bounding edges; (ii) a cluster $V_*$ containing a vertex $v_i$ for each point $p_i \in \mathcal {P}$, plus vertices $v_\alpha$ and $v_\omega$; (iii) corner edges connecting $v_{tl}$, $v'_{tr}$, $v''_{tr}$, $v_{br}$, $v'_{bl}$, and $v''_{bl}$ with either $v_\alpha$ or $v_\omega$; and (iv) for every chord $c = (p_i,p_j) \in \mathcal {O}$, a path corresponding to c composed of a cluster $\{v_c\}$ and of two chord edges $(v_i,v_c)$ and $(v_c,v_j)$. Let the row-column order $\sigma _{*}$ of $V_*$ be $v_\alpha ,\mathcal {P},v_\omega$. We now prove the equivalence between the instances.

($\Longrightarrow$) Suppose that the chords of $\langle \mathcal {P}, \mathcal {O} \rangle$ can be assigned colors 1, 2, 3, 4 so that no two chords with the same color cross. Embed D in the plane and embed the matrix $M_*$ representing $V_*$ inside D with row-column order $\sigma _*$. Route the corner edges inside D, subdividing the region inside D and outside $M_*$ into four regions, each incident to a distinct side of $M_*$. Arbitrarily color these four regions with colors 1, 2, 3, 4; embed a path $(v_i,v_c,v_j)$ inside a region if the chord $(p_i,p_j)$ corresponding to $(v_i,v_c,v_j)$ has the color of the region. Then only paths in the same region might intersect, however if they do then they correspond to chords with the same color that cross in $\langle \mathcal {P}, \mathcal {O} \rangle$, given that the order of the vertices in $\sigma _*$ is the same as the order of the corresponding points in $\mathcal {P}$.

($\Longleftarrow$) Suppose that $(V, E, \mathcal {C})$ has a planar NT representation $\varGamma$ with row-column order $\sigma _*$ for the matrix $M_*$ representing $V_*$. Since $v_{\alpha }$ and $v_{\omega }$ are the first and last vertex in $\sigma _*$, the corner edges subdivide the region inside D and outside $M_*$ into four regions, each incident to a distinct side of $M_*$, which we arbitrarily color 1, 2, 3, 4. By the planarity of $\varGamma$, each path $(v_i, v_c, v_j)$ is in one of such regions; then we color each chord $(p_i,p_j)$ with the color of the region path $(v_i, v_c, v_j)$ is embedded into. If two chords with the same color cross in $\langle \mathcal {P}, \mathcal {O} \rangle$, then the corresponding paths cross in $\varGamma$, as the order of the vertices in $\sigma _*$ is the same as the order of the corresponding points in $\mathcal {P}$.    $\square$

Let $G=(V,E,\mathcal {C})$ be a flat clustered graph with a given row-column order $\sigma _i$ and side assignment $s_i$, for each $V_i \in \mathcal {C}$. Then G is NT planar with fixed order and fixed side if it is simultaneously planar with fixed order and with fixed side.

Theorem 4

NodeTrix Planarity with Fixed Order and Fixed Side can be solved in linear time.

Proof Sketch:

Consider the graph $G'$ obtained from an instance $G=(V,E,\mathcal {C})$ by collapsing each cluster $V_i$ into a vertex $v_i$. Instance G is NT planar with fixed order and fixed side if and only if $G'$ is planar with the additional constraint that the clockwise order of the edges incident to each vertex $v_i$ is compatible with the order of the rows of the matrix representing $V_i$ and the side assignment for each inter-cluster edge incident to $V_i$. We obtain an instance of constrained planarity that can be tested in linear time with known techniques [15].    $\square$

We conclude the section with the following lemma.

Lemma 1

NodeTrix Planarity, NodeTrix Planarity with Fixed Side, and NodeTrix Planarity with Fixed Order are in $\mathbb {NP}$.

Proof Sketch:

The number of distinct row-column orders and side assignments for an instance $(V,E,\mathcal {C})$ is a function of $|V|+|E|$. The statement follows from Theorem 4.    $\square$

3 Monotone NodeTrix Representations

Let $G=(V,E,\mathcal {C})$ be a flat clustered graph and $\gamma$ be a square assignment for G that maps each cluster in $\mathcal C$ to an axis-aligned square in the plane. A curve is x-monotone (resp. y-monotone) if no two of its points have the same projection on the x-axis (resp. on the y-axis) and is xy-monotone if it is either a horizontal or a vertical segment or it is both x- and y-monotone. A monotone NT representation $\varGamma$ of $\langle G, \gamma \rangle$ is a NT representation such that: (i) all the inter-cluster edges are represented by xy-monotone curves; (ii) the boundary of the matrix $M_i$ representing cluster $V_i \in \mathcal{C}$ is $Q_i=\gamma (V_i)$; (iii) for each pair of adjacent clusters $V_i$ and $V_j$, with $i\ne j$, the convex hull of $Q_i$ and $Q_j$ does not intersect any other $Q_k$, with $k\ne i, j$ – we call this convex hull the pipe of $Q_i$ and $Q_j$; and (iv) all the inter-cluster edges between vertices in $V_i$ and vertices in $V_j$ lie inside the pipe of $Q_i$ and $Q_j$. In a monotone NT representation $\varGamma$ of G let $\chi _i(\varGamma )$ denote the number of edge crossings between pairs of inter-cluster edges incident to $V_i$. Let $\chi (\varGamma ) = \sum _{i=1}^k \chi _i(\varGamma )$; we say that $\varGamma$ is locally planar if $\chi (\varGamma )=0$ and no inter-cluster edge intersects any matrix except at its incidence points. The notions of fixed order and fixed side easily extend to monotone NT representations.

We study the complexity of testing if a flat clustered graph with fixed square assignment admits a monotone locally-planar NT representation, a problem which we call Monotone NT Local Planarity (MNTLP). The next two theorems show the $\mathbb {NP}$-hardness of MNTLP and of its variant with fixed side.

Theorem 5

MNTLP is $\mathbb {NP}$-complete.

Theorem 6

MNTLP with Fixed Side is $\mathbb {NP}$-complete.

Since the instances of MNTLP used in the proof of Theorem 5 are planar whenever they are locally planar, testing the existence of a planar monotone NT representation with fixed square assignment is also $\mathbb {NP}$-complete. Further, the instances of NT Planarity used in the proof of Theorem 1 can be drawn planarly with straight-line (i.e., monotone) edges, whenever they are planar. Hence, testing whether a flat clustered graph admits a monotone planar NT representation – without square assignment – is $\mathbb {NP}$-complete.

Consider now a flat clustered graph $G=(V,E,\mathcal {C})$ and a monotone NT representation $\varGamma$ of G with fixed square assignment $\gamma$. Consider two clusters $V_a,V_b\in \mathcal {C}$ and let $Q_a=\gamma (V_a)$ and $Q_b=\gamma (V_b)$. Since $Q_a$ and $Q_b$ are disjoint, there exists either a vertical or a horizontal line separating them. Suppose that the former holds, the other case being analogous. Also suppose that $\max _x(Q_a) < \min _x(Q_b)$ and $\max _y(Q_a) \ge \max _y(Q_b)$, the other cases being analogous up to reflections of the Cartesian axes (refer to Fig. 4). Also, consider an inter-cluster edge $e = (u,v) \in E_{a,b}$. Depending on the relative positions of $Q_a$ and $Q_b$ in $\varGamma$, not all the possible combinations of side assignments for e might be allowed, as described in the following property.

Property 1

Let $y_u$ and $y_v$ be the y-coordinate of points $m_\textsc {r}^u$ and $m_\textsc {l}^v$, respectively. The following three arrangements are possible for $Q_a$ and $Q_b$ in $\varGamma$.

Arrangement 1: $\max _y(Q_b) < \min _y(Q_a)$. Then $s_b(e)\ne \textsc {b}$ and all other four side assignments $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {t} \rangle$, $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {l} \rangle$, $\langle s_a(e)=\textsc {b}, s_b(e)=\textsc {t} \rangle$, and $\langle s_a(e)=\textsc {b}, s_b(e)=\textsc {l} \rangle$ are allowed for e.

Arrangement 2: $\min _y(Q_b)< \min _y(Q_a)\le \max _y(Q_b)$. Then $s_b(e)\ne \textsc {b}$; also, pair $\langle s_a(e)=\textsc {b}, s_b(e)=\textsc {t} \rangle$ is not allowed, while pair $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {l} \rangle$ is allowed. The remaining two possible pairs $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {t} \rangle$ and $\langle s_a(e)=\textsc {b}, s_b(e)=\textsc {l} \rangle$ are or are not allowed, depending on $y_u$ and $y_v$. In particular, if $y_u \le \max _y(Q_b)$, then $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {t} \rangle$ is not allow+ed, otherwise it is; also, if $y_v \ge \min _y(Q_a)$, then $\langle s_a(e)=\textsc {b}, s_b(e)=\textsc {l} \rangle$ is not allowed, otherwise it is.

Arrangement 3: $\min _y(Q_a)\le \min _y(Q_b)$. Then $s_a(e)\ne \textsc {b}$; also, pair $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {l} \rangle$ is allowed. The remaining two possible pairs $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {t} \rangle$ and $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {b} \rangle$ are or are not allowed, depending on $y_u$. In particular, if $y_u \le \max _y(Q_b)$, then $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {t} \rangle$ is not allowed, otherwise it is, and if $y_u \ge \min _y(Q_b)$, then $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {b} \rangle$ is not allowed, otherwise it is.

Fig. 4.

Possible arrangements of squares $Q_a$ and $Q_b$. Thick red segments represent sides of $Q_a$ and $Q_b$ edge (u, v) cannot be assigned to. Red curves show further forbidden side assignment pairs for edge (u, v).eps (Color figure online)

Note that if an edge e can be drawn as an xy-monotone curve not crossing any matrix then it can also be drawn as a straight-line segment not crossing any matrix, since the pipe of $Q_a$ and $Q_b$ does not intersect any matrix other than $M_a$ and $M_b$. The next lemma extends this observation by arguing that the xy-monotonicity constraint can be replaced by a straight-line requirement also for what concerns crossings between inter-cluster edges incident to the same matrix.

Lemma 2

An instance $\langle G=(V,E,\mathcal {C}),\gamma \rangle$ of MNTLP with Fixed Order and Fixed Side is locally planar if and only if it admits a locally planar monotone NT representation where all the inter-cluster edges are drawn as straight-line segments.

In contrast to the negative results of Theorems 5 and 6, we show that MNTLP with Fixed Order and Fixed Side is solvable in polynomial time.

Theorem 7

MNTLP with Fixed Order and Fixed Side can be solved in polynomial time.

Proof:

We check whether every edge can be represented as an xy-monotone curve by Property 1. Further, we check whether all pairs of inter-cluster edges incident to the same cluster admit a non-crossing straight-line drawing by Lemma 2.    $\square$

The remaining piece of the complexity puzzle for MNTLP is the setting with fixed row-column order and free side assignment. Although we are not able to establish the complexity of the corresponding decision problem, we show that testing MNTLP with fixed order is polynomial-time solvable if the number of clusters is constant. In order to do that, we show how to transform instances of our problem into instances of 2-SAT.

Assuming the hypotheses stated before Property 1 about the relative position of $Q_a$ and $Q_b$, we say that an inter-cluster edge $e = (u \in V_a, v \in V_b)$ is S-drawn in $\varGamma$ if: (i) $Q_a$ and $Q_b$ are arranged as in Arrangement 1 of Property 1 and either $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {l} \rangle$ or $\langle s_a(e)=\textsc {b}, s_b(e)=\textsc {t} \rangle$; or (ii) $Q_a$ and $Q_b$ are arranged as in Arrangement 2 of Property 1 and it holds that (a) $\langle s_a(e)=\textsc {r}, s_b(e)=\textsc {l} \rangle$, (b) $y_u>\max _y(Q_b)$, and (c) $y_v<min_y(Q_a)$. Note that if $Q_a$ and $Q_b$ are arranged as in Arrangement 3 of Property 1, then e is not S-drawn in $\varGamma$, by definition. The representation of an S-drawn edge is an S-drawing. We have the following.

Lemma 3

Let $\langle G=(V,E,\mathcal {C}=\{V_a,V_b\}), \gamma , \sigma \rangle$ be an instance of MNTLP with Fixed Order. Consider the following two cases: an inter-cluster edge $e^* \in E$ has a given S-drawing $\varGamma _e$ (Case 1), or no inter-cluster edge in E has an S-drawing (Case 2). Both in Case 1 and in Case 2, we can construct in $O(|E|^2)$ time a 2-SAT formula $\phi (a,b,\varGamma _e)$ and $\phi (a,b)$, respectively, with length $O(|E|^2)$ that is satisfiable if and only if $\langle G, \gamma , \sigma \rangle$ admits a locally planar monotone NT representation with fixed order satisfying the constraint of the corresponding case.

Proof Sketch:

If $Q_a=\gamma (V_a)$ and $Q_b=\gamma (V_b)$ are not disjoint, no NT representation of G exists, hence the statement is trivially true. Otherwise, there exists either a vertical or a horizontal line separating them. Suppose that the former holds and that $\max _x(Q_a) < \min _x(Q_b)$ and $\max _y(Q_a) \ge \max _y(Q_b)$, the other cases being analogous. Suppose that an inter-cluster edge $e^*$ is required to have a drawing $\varGamma _e$ as in Case 1. By the definition of an S-drawn edge, if $Q_a$ and $Q_b$ are arranged as in Arrangement 3 of Property 1, the required NT representation does not exist, thus the statement trivially holds. Hence, we can assume that $Q_a$ and $Q_b$ are arranged as in Arrangement 1 or 2 of Property 1. Let $e \ne e^* \in E$ be any inter-cluster edge not adjacent to e.

Consider Arrangement 1 and suppose $s_a(e^*)=\textsc {r}$ and $s_b(e^*)=\textsc {l}$. The end-vertices of e and $e^*$ in $V_a$ (in $V_b$) have two possible relative positions in $\sigma _a$ (resp. in $\sigma _b$). This leads to four possible combinations for these relative positions.

If $\sigma _a(e^*) < \sigma _a(e)$ and $\sigma _b(e) < \sigma _b(e^*)$, then any xy-monotone curve representing e crosses $e^*$ independently of the side assignment for e and the statement trivially holds. See Fig. 5a. For each of the three remaining combinations, exactly two side assignments for e create no crossing with $e^*$. If $\sigma _a(e) < \sigma _a(e^*)$ and $\sigma _b(e) < \sigma _b(e^*)$, then it holds that either $s_a(e)=\textsc {r}$ and $s_b(e) = \textsc {t}$ or $s_a(e)=\textsc {r}$ and $s_b(e) = \textsc {l}$. See Fig. 5b. If $\sigma _a(e) < \sigma _a(e^*)$ and $\sigma _b(e^*) < \sigma _b(e)$, then it holds that either $s_a(e)=\textsc {r}$ and $s_b(e) = \textsc {t}$ or $s_a(e)=\textsc {b}$ and $s_b(e) = \textsc {l}$. See Fig. 5c. If $\sigma _a(e^*) < \sigma _a(e)$ and $\sigma _b(e^*) < \sigma _b(e)$, then it holds that either $s_a(e)=\textsc {r}$ and $s_b(e) = \textsc {l}$ or $s_a(e)=\textsc {b}$ and $s_b(e) = \textsc {l}$. See Fig. 5d.

The case in which $Q_a$ and $Q_b$ are arranged as in Arrangement 1, $s_a(e^*)=\textsc {b}$, and $s_b(e^*)=\textsc {t}$ is analogous. The proof for Arrangement 2 is also analogous.

We are now ready to show, for Case 1 of the lemma, that a locally planar monotone NT representation of $\langle G=(V,E,\mathcal {C}=\{V_a,V_b\}), \gamma \rangle$ with $s_a(e^*)=\textsc {r}$ and $s_b(e^*)=\textsc {l}$ exists if and only if a suitable 2-SAT formula $\phi$ is satisfiable. For each inter-cluster edge $e \ne e^* \in E$ not adjacent to $e^*$, we define a Boolean variable $x_e$. The above discussion shows that, if a trivially false formula cannot be associated with the instance $\langle G, \gamma , \sigma \rangle$, then there are exactly two distinct side assignments for e. We select one arbitrarily, which we call canonical side assignment, and associate $x_e={\textsc {true}}$ to it and $x_e={\textsc {false}}$ to the other. For each pair of non-adjacent inter-cluster edges $e_1,e_2 \ne e^* \in E$, consider the four possible side assignments for them. We add to $\phi$ at most four clauses defined as follows. If the canonical side assignment for $e_1$ and the one for $e_2$ generate a crossing between $e_1$ and $e_2$, then we add clause $\{\overline{x_{e_1}} \vee \overline{x_{e_2}}\}$ to $\phi$. If the canonical side assignment for $e_1$ and the non-canonical side assignment for $e_2$ generate a crossing between $e_1$ and $e_2$, then we add clause $\{\overline{x_{e_1}} \vee x_{e_2}\}$ to $\phi$. If the non-canonical side assignment for $e_1$ and the canonical side assignment for $e_2$ generate a crossing between $e_1$ and $e_2$, then we add clause $\{x_{e_1} \vee \overline{x_{e_2}}\}$ to $\phi$. If the non-canonical side assignment for $e_1$ and the one for $e_2$ generate a crossing between $e_1$ and $e_2$, then we add clause $\{x_{e_1} \vee x_{e_2}\}$ to $\phi$.

As a consequence of the above discussion $\langle G=(V,E,\mathcal {C}=\{V_a,V_b\}), \gamma \rangle$ admits a locally planar monotone NT representation such that $s_a(e^*)=\textsc {r}$ and $s_b(e^*)=\textsc {l}$ if and only if $\phi$ is satisfiable. Further, since the number of clauses in $\phi$ is upper-bounded by $O(|E|^2)$ and since it can be determined in constant time whether a side assignment for any two edges produces a crossing, then formula $\phi$ can be constructed in $O(|E|^2)$ time and has $O(|E|^2)$ size. Since 2-SAT formulae can be tested for satisfiability in linear time [8], the statement of Case 1 follows if $s_a(e^*)=\textsc {r}$ and $s_b(e^*)=\textsc {l}$; a 2-SAT formula can be analogously constructed if $s_a(e^*)=\textsc {b}$ and $s_b(e^*)=\textsc {t}$.

The discussion of Case 2 and the corresponding construction of the Boolean formula are analogous to those of Case 1.    $\square$

Fig. 5.

Illustrations for the proof of Lemma 3, Case 1, Arrangement 1.

We now turn to the study of flat clustered graphs with three clusters.

Lemma 4

Let $\langle G=(V,E,\mathcal {C}=\{V_a,V_b,V_c\}), \gamma , \sigma \rangle$ be an instance of MNTLP with Fixed Order. Consider the four cases that are generated by assuming that an edge $e^* \in E_{a,b}$ has a prescribed S-drawing or not and that an edge $f^* \in E_{a,c}$ has a prescribed S-drawing or not. In each case, we can construct in $O(|E|^2)$ time a 2-SAT formula with length $O(|E|^2)$ that is satisfiable if and only if $\langle G, \gamma , \sigma \rangle$ admits a monotone NT representation with fixed order that satisfies the constraints of the corresponding case, such that no inter-cluster edge intersects any matrix except at its incidence points, and such that there are no two edges, one in $E_{a,b}$ and one in $E_{a,c}$, that cross each other.

Proof:

In each of the four cases, the hypotheses lead us in either Case 1 or Case 2 of Lemma 3 for the edges in $E_{a,b}$ and the same holds for the edges in $E_{a,c}$. Hence, by Lemma 3, each of these edges admits at most two side assignments in each case. Moreover, each of these side assignments corresponds to a directed or negated literal. For each pair of edges $e\in E_{a,b}$ and $f\in E_{a,c}$ and for each of the at most four side assignments for them, we exploit Lemma 2 to test whether a side assignment for e and f leads to a crossing and in the case of a crossing we introduce suitable clauses to rule out that side assignment.    $\square$

We finally get the following.

Theorem 8

MNTLP with Fixed Ordering can be tested in $O(\left( {\begin{array}{c}|2E+1|\\ |\mathcal {C}|^2\end{array}}\right) |E|^2)$ time for an instance $\langle G=(V,E,\mathcal {C}), \gamma , \sigma \rangle$.

Proof Sketch:

The proof is based on guessing, for each pair of adjacent clusters, whether they are connected by an S-drawn edge or not. For each guess we exploit Lemmata 3 and 4 to construct a 2-SAT formula that is checked for satisfiability. For each pair of adjacent clusters $V_a,V_b$ we have to guess among $2|E_{a,b}|+1$ possibilities, corresponding to the choice of $|E_{a,b}|$ edges to be S-drawn, each in two possible ways, plus the possibility of not having any S-drawn edge. This leads to $O(\left( {\begin{array}{c}|2E+1|\\ |\mathcal {C}|^2\end{array}}\right) )$ guesses.    $\square$

Observe that the computational complexity of the algorithm described in the proof of Theorem 8 is polynomial if the number of clusters is constant.

4 Conclusions and Open Problems

We have shown that testing NodeTrix (NT) representations of clustered graphs for planarity is $\mathbb {NP}$-complete even if the order of the rows and columns is fixed or if the sides where the inter-cluster edges attach to the matrices is fixed. We have also studied the setting where matrices have fixed positions and inter-cluster edges are xy-monotone curves. In this case we established negative and positive results; leveraging on the latter, we developed a library that computes a layout of the inter-cluster edges with few crossings. A demo [3] shows that the computation allows the user to move matrices without any slowdown of the interaction.

Several theoretical problems are related to the planarity of NT representations. First, the $\mathbb {NP}$-completeness of NT planarity can be interpreted as a proof of the $\mathbb {NP}$-completeness of clustered planarity (see, for example, [4, 6, 11, 14]) when a specific type of representation is required. Observe, though, that a flat clustered graph may be NT planar even if its underlying graph is not planar. Second, planarity of hybrid representations have been recently studied [5] in the setting in which clusters are represented as the intersections of geometric objects. Our results can be viewed as a further progress in this area. Third, consider a clustered graph with two clusters represented as matrices aligned along their principal diagonal. Computing a locally planar NT representation is equivalent to solve the 2-page bipartite book embedding with spine crossings problem [5]. Interestingly, if the two matrices are aligned along their secondary diagonal this equivalence is not evident anymore.

Among the future research directions, we mention the one of automatically embedding the matrices to minimize crossings in monotone NT representations.