2026-08-12T05:29:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1556 2024-03-06T11:08:07Z ddc:004 open_access

08191 Working Group Report – X-graphs of Y-graphs and their Representations Batagelj, Vladimir Brandenburg, Franz J. Didimo, Walter Liotta, Guiseppe Patrignani, Maurizio Graph drawing X-graphs of Y-graphs visualization of large graphs 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 by Brandenburg (Brandenburg, F.J.: Graph clustering I: Cycles of cliques. In Di Battista, G., ed.: Graph Drawing (Proc. GD '97). Volume 1353 of Lecture Notes Comput. Sci., Springer-Verlag (1997) 158--168) to formalize the problem 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, $K_5$)-recognition, that is, the problem of identifying $K_5$ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vladimir Batagelj and Franz J. Brandenburg and Walter Didimo and Guiseppe Liotta and Maurizio Patrignani 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.08191.5 urn:nbn:de:0030-drops-15563 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.5 eng https://creativecommons.org/licenses/by/4.0/legalcode