1 January 2017 in SIAM Journal on Computing
Given an $n$-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) betw...
1 April 2015 in Theoretical Computer Science
1 February 2017 in Journal of Graph Algorithms and Applications
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 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 ${\rm C{\small LIQUE} P{\small LANARITY}}$, for intersection-link representations of graphs in which the dense subgraphs are cliques.
1 March 2015 in Theoretical Computer Science
8 February 2016 in Algorithmica
1 January 2018 in Journal of Graph Algorithms and Applications
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.