License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-15563
URL: https://drops.dagstuhl.de/opus/volltexte/2008/1556/
Go to the corresponding Portal


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:
08191.SWM.Paper.1556.pdf (0.4 MB)


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
Collection: 08191 - Graph Drawing with Applications to Bioinformatics and Social Sciences
Issue Date: 2008
Date of publication: 22.07.2008


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI