X-graphs of Y-graphs and their Representations ⋆
Vladimir Batagelj, Franz Josef Brandenburg, Walter Didimo, Giuseppe Liotta, Maurizio Patrignani · 2008
We address graph decomposition problems that help the hybrid visualization of large graphs, where different graphic metaphors (node-link, matrix, etc.) are used in the same picture. We generalize the X-graphs of Y-graphs model introduced in [1] to formalize the prob-lem of automatically identifying dense subgraphs (Y-graphs, clusters) that are prone to be collapsed and shown with a matricial representation when needed. We show that (planar, K5)-recognition, that is, the problem of identifying K5 subgraphs such that the graph obtained by collapsing them is planar, is NP-hard. On the positive side, we show that it is possible to determine the highest value of k such that G is a (planar,k-core)-graph in O(m + n log(n)) time.