Title: NodeTrix Planarity Testing with Small Clusters,
Abstract: We study the NodeTrix planarity testing problem for flat clustered graphs
when the maximum size of each cluster is bounded by a constant $k$. We consider
both the case when the sides of the matrices to which the edges are incident
are fixed and the case when they can be arbitrarily chosen. We show that
NodeTrix planarity testing with fixed sides can be solved in
$O(k^{3k+\frac{3}{2}} n^3)$ time for every flat clustered graph that can be
reduced to a partial 2-tree by collapsing its clusters into single vertices. In
the general case, NodeTrix planarity testing with fixed sides can be solved in
$O(n^3)$ time for $k = 2$, but it is NP-complete for any $k \geq 3$. NodeTrix
planarity testing remains NP-complete also in the free side model when $k > 4$.