License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-15563
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1556/
Batagelj, Vladimir ; Brandenburg, Franz J. ; Didimo, Walter ; Liotta, Guiseppe ; Patrignani, Maurizio

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

pdf-format:
Dokument 1.pdf (378 KB)

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.

BibTeX - Entry

@InProceedings{batagelj_et_al:DSP:2008:1556,
  author =	{Vladimir Batagelj and Franz J. Brandenburg and Walter Didimo and Guiseppe Liotta and Maurizio Patrignani},
  title =	{08191 Working Group Report -- X-graphs of Y-graphs and their Representations},
  booktitle =	{Graph Drawing with Applications to Bioinformatics and Social Sciences},
  year =	{2008},
  editor =	{Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel},
  number =	{08191},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1556},
  annote =	{Keywords: Graph drawing, X-graphs of Y-graphs, visualization of large graphs}
}

Keywords: Graph drawing, X-graphs of Y-graphs, visualization of large graphs
Seminar: 08191 - Graph Drawing with Applications to Bioinformatics and Social Sciences
Issue date: 2008
Date of publication: 22.07.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI