DROPS

Document

08191 Working Group Report – X-graphs of Y-graphs and their Representations

Authors: Vladimir Batagelj, Franz J. Brandenburg, Walter Didimo, Guiseppe Liotta, and Maurizio Patrignani

Published in: Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)

Abstract

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.

Cite as

Vladimir Batagelj, Franz J. Brandenburg, Walter Didimo, Guiseppe Liotta, and Maurizio Patrignani. 08191 Working Group Report – X-graphs of Y-graphs and their Representations. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{batagelj_et_al:DagSemProc.08191.5,
  author =	{Batagelj, Vladimir and Brandenburg, Franz J. and Didimo, Walter and Liotta, Guiseppe and Patrignani, Maurizio},
  title =	{{08191 Working Group Report – X-graphs of Y-graphs and their Representations}},
  booktitle =	{Graph Drawing with Applications to Bioinformatics and Social Sciences},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8191},
  editor =	{Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.5},
  URN =		{urn:nbn:de:0030-drops-15563},
  doi =		{10.4230/DagSemProc.08191.5},
  annote =	{Keywords: Graph drawing, X-graphs of Y-graphs, visualization of large graphs}
}

Search Results

Documents authored by Liotta, Guiseppe

08191 Working Group Report – X-graphs of Y-graphs and their Representations

Abstract

Cite as

Thanks for your feedback!

Could not send message