Batagelj, Vladimir ;
Brandenburg, Franz J. ;
Didimo, Walter ;
Liotta, Guiseppe ;
Patrignani, Maurizio
08191 Working Group Report  Xgraphs of Ygraphs and their Representations
Abstract
We address graph decomposition problems that help the hybrid visualization of large
graphs, where different graphic metaphors (nodelink, 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., SpringerVerlag
(1997) 158168) 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 NPhard. 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  Xgraphs of Ygraphs 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 = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1556},
annote = {Keywords: Graph drawing, Xgraphs of Ygraphs, visualization of large graphs}
}
2008
Keywords: 

Graph drawing, Xgraphs of Ygraphs, visualization of large graphs 
Seminar: 

08191  Graph Drawing with Applications to Bioinformatics and Social Sciences

Related Scholarly Article: 


Issue date: 

2008 
Date of publication: 

2008 