License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08191.5
URN: urn:nbn:de:0030-drops-15563
URL: http://dagstuhl.sunsite.rwth-aachen.de/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: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/opus/volltexte/2008/1556},
  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}
}

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