Geodesic
Generalizing Geometric Graphs
Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 1, pp. 35-76.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Network visualization is essential for understanding the data obtained from huge real-world networks such as flight-networks, the AS-network or social networks. Although we can compute layouts for these networks reasonably fast, even the most recent display media are not capable of displaying these layouts in an adequate way. Moreover, the human viewer may be overwhelmed by the displayed level of detail. The increasing amount of data therefore requires techniques aiming at a sensible reduction of the visual complexity of huge layouts. We consider the problem of computing a generalization of a given layout reducing the complexity of the drawing to an amount that can be displayed without clutter and handled by a human viewer. We take a first step at formulating graph generalization within a mathematical model and we consider the resulting problems from an algorithmic point of view. We show that these problems are NP-hard in general, and provide efficient approximation algorithms as well as efficient and effective heuristics. We also showcase some sample generalizations.
DOI : 10.7155/jgaa.00314
Keywords: geometric graph, generalization, visual complexity, data reduction, abstraction, optimization, algorithm, heuristic 
@article{JGAA_2014_18_1_a1,
     author = {Edith Brunel and Andreas Gemsa and Marcus Krug and Ignaz Rutter and Dorothea Wagner},
     title = {Generalizing {Geometric} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {35--76},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2014},
     doi = {10.7155/jgaa.00314},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00314/}
}
TY  - JOUR
AU  - Edith Brunel
AU  - Andreas Gemsa
AU  - Marcus Krug
AU  - Ignaz Rutter
AU  - Dorothea Wagner
TI  - Generalizing Geometric Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2014
SP  - 35
EP  - 76
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00314/
DO  - 10.7155/jgaa.00314
LA  - en
ID  - JGAA_2014_18_1_a1
ER  - 
%0 Journal Article
%A Edith Brunel
%A Andreas Gemsa
%A Marcus Krug
%A Ignaz Rutter
%A Dorothea Wagner
%T Generalizing Geometric Graphs
%J Journal of Graph Algorithms and Applications
%D 2014
%P 35-76
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00314/
%R 10.7155/jgaa.00314
%G en
%F JGAA_2014_18_1_a1
Edith Brunel; Andreas Gemsa; Marcus Krug; Ignaz Rutter; Dorothea Wagner. Generalizing Geometric Graphs. Journal of Graph Algorithms and Applications, Tome 18 (2014) no. 1, pp. 35-76. doi : 10.7155/jgaa.00314. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00314/

Cité par Sources :