Computing NodeTrix Representations of Clustered Graphs
Vol. 22, no. 2, pp. 139-176, 2018. Regular paper.
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. Building on such algorithms we develop a JavaScript library for NodeTrix representations aimed at reducing the crossings between edges incident to the same matrix.
Submitted: November 2016.
Reviewed: October 2017.
Revised: November 2017.
Accepted: December 2017.
Published: January 2018.
Communicated by Giuseppe Liotta
article (PDF)