Programma del Corso

Si tenga presente che, anche se un argomento non e' trattato sulle dispense ne' sulle tesine, questo NON e' un buon motivo per non studiarlo. Inoltre, si consiglia di affiancare comunque i testi consigliati alle dispense e ai lucidi.

N.B. Le parti di testo blu sono argomenti facoltativi

1. Definizioni preliminari

  • Breve storia della visualizzazione di oggetti nei secoli
  • Modellizzazione teorica degli oggetti da rappresentare; differenza tra oggetto e sua rappresentazione
  • Definizioni di base di teroria dei grafi
  • Convenzioni (polyline, ortogonale, rettilinea, planare, upward, tridimensionale); criteri estetici (numero di incroci, area, numero di svolte, lunghezza degli archi, simmetrie, risoluzione angolare); precedenze tra i criteri estetici; vincoli (richiesta di posizionare un vertice al centro o sul contorno della rappresentazione, richiesta di raggruppare -clustering- vertici secondo alcuni criteri, richiesta di mantenere una certa forma).

Materiale didattico di riferimento:

  • E. Kruja, J. Marks, A. Blair, R. Waters: "A Short note on the history of Graph Drawing"; Proc. Graph Drawing (GD01), LNCS 2265, pp. 272-286, 2001.
  • C. Chen: Information Visualization beyond the horizon � 2nd Edition, Springer 2004, pp. 8-10.
  • G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing Algorithms for the visualization of graphs, Prentice Hall, 1999, pp. 1-18.
  • M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 1-22.

2. Visualizzazione di oggetti con struttura ad albero

  • Esempio di oggetti con struttura ad albero: mappa di un file system, indice di una base di dati, alberi genealogici.
  • Terminologia per gli alberi.
  • Visualizzazione ortogonale ottima come H-tree
  • Un algoritmo di disegno upward planare basato sul livellamento dell'albero, con nodi a coordinate intere
  • Un algoritmo di disegno upward planare piu' efficiente
  • Un algoritmo di disegno radiale
  • Un algoritmo di disegno HV
  • Visualizzazione di gerarchie: tree maps, sun bursts, cone trees, alberi botanici

Materiale didattico di riferimento:

  • G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing Algorithms for the visualization of graphs, Prentice Hall, 1999, pp. 41-60.
  • Leiserson: Area-efficient graph layouts (for VLSI), Proc. 21th IEEE Symp. On Found. Of Compu. Sci (FOCS'80), pp. 270-281, 1980.
  • M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 46-52.
  • A. Garg, M.T. Goodrich, R. Tamassia: "Planar Upward Tree Drawings with Optimal Area", Internat. J. Comput. Geom. Appl., 6, 333-356, 1996, pp. 2-6.
  • C. Chen: Information Visualization beyond the horizon � 2nd Edition, Springer 2004, pp 89-95, e pp.190-193;
  • B.B. Bederson, B. Shneiderman and M. Wattenberg. Ordered and Quantum Trremaps: Making Effective Use of 2D Space to Display Hierarchies. ACM Trans. Graph. 21(4), 833-854, 2002, pp. 833-837;
  • G.G. Robertson, J.D. Mackinlay and S.K. Card. Cone Trees: animated 3D visualizations of hierarchical information. ACM ??? , 189-194, 1991, pp 189-191.

3a. Visualizzazione di grafi: alcuni casi particolari

  • Disegno ortogonale 2D: Codifiche di grafi; st-numerazione; Un algoritmo basato sulla st-numerazione; Un algoritmo basato sulla rappresentazione di visibilita'. Algoritmo di st-numerazione.
  • Disegno ortogonale 3D: Punto di vista; Alcune premesse di teoria dei grafi (caratterizzazione dei cicli euleriani e teorema di P. Hall, dim. del teorema di Eulero e dim. del teorema di P. Hall); Due algoritmi di disegno 3D ortogonale.
  • Disegno rettilineo 3D: Un algoritmo di disegno rettilineo e limitazione inferiore sul volume per grafi generali; algoritmo e limitazione inferiore per grafi 2-, 3- e 4-partiti. Teorema sulla limitazione inferiore del volume come funzione del numero di archi del grafo.
  • Disegno ortogonale interattivo: mantenere la mappa mentale; gli scenari del disegno interattivo; un algoritmo per dis. ortogonale su griglia 2d nello scenario relative-coordinates e uno nello scenario no-change; confronto tra i due scenari.
  • Visualizzazione di grafi in evoluzione (network evolution).

Materiale didattico di riferimento:

  • M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 121-141, esclusa sez. 6.2, 172, 176-180, 190-192, 228-240. PER APPROFONDIRE: pagg. 182-189.
  • G. Di Battista, R. Tamassia: Algorithms for Plane Representations of acyclic digraphs, Theoretical Computer Science 61, pp 175-198, 1988. solo sezioni 1, 2 e, della sezione 3, solo i teoremi 3.4, 3.5 e figura 12.
  • Nishizeki, T., Chiba, N.: "Planar graphs: theory and algorithms", North-Holland, Amsterdam, 1988, pp.34-40.
  • T. Biedl, G.Kant: "A better heuristic for orthogonal graph drawings", Proc. 2nd European Symp. on Algorithms (ESA'94), LNCS 855, pp.24-35.
  • P. Eades, A. Symvonis, S. Whitesides: Two Algorithms for Three Dimensional Orthogonal Graph Drawing;, Proc. Graph Drawing (GD�96) LNCS 1190, pp. 139-154, 1996 tutto.
  • un qualunque testo di teoria dei grafi per la caratterizzazione dei circuiti euleruani e il teorema di P. Hall.
  • Cohen, Eades, Lin, Ruskey: 'Three-Dimensional Graph Drawing", Proc. Graph Drawing '94, LNCS 894, pp. 1-11, 1994. Solo sezioni 1 e 2, esclusa dimostrazione del teorema 1
  • G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing; Algorithms for the visualization of graphs, Prentice Hall, 1999, pp. 99-102, 130-132, 137-138, 218-235.
  • C. Chen: Information Visualization beyond the horizon, Springer, 2004, pp. 278-282.
  • T. Calamoneri, A. Sterbini: 3D straigh-line drawing of 4-colorable graphs, Information Proc. Letters 63, pp. 97-102, 1997 tutto.

3b. Generalizzazione della visualizzazione di grafi: il caso particolare del disegno ortogonale

  • Esempi di estensione al caso di grado alto (2D ortogonale planare, 2D ortogonale non planare e 3D ortogonale);
  • Esempi di estensione da grafi biconnessi a semplicemente connessi;
  • Esempi di estensione da grafi planari a non planari.

Materiale didattico di riferimento:

  • G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing; Algorithms for the visualization of graphs, Prentice Hall, 1999, pp.168-169, 215-216, 253-262.
  • M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 29-33.
  • T.Biedl, T.Shermer, S.Whitesides, S.Wismath: "Orthogonal 3-D Graph Drawing", Proc. Graph Drawing (GD'97), LNCS 1353, pp. 76-86, 1997.
  • T. Biedl, G.Kant: "A better heuristic for orthogonal graph drawings", Proc. 2nd European Symp. on Algorithms (ESA'94), LNCS 855, pp.24-35 (gią citato in precedenza).

3c. Ottimizzazione della visualizzazione di grafi: il caso particolare del disegno ortogonale

  • Minimizzazione del numero di svolte: euristiche;
  • Compattamento dell'area: metodo del flusso.

Materiale didattico di riferimento:

  • G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing; Algorithms for the visualization of graphs, Prentice Hall, 1999, pp. 143-154, 157-161.
  • PER APPROFONDIRE: pp. 164-168.
  • M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 167-169 (escluso alg. delle 4M).
  • PER APPROFONDIRE: pp.147-167.

4. Visualizzazione di strutture molecolari

  • Algoritmi basati sulla ricerca del punto di minimo delle forze di interazione: algoritmo di Garg e algoritmo di Tutte
  • Generalizzazione di Sugiyama e Misue, generalizzazione di Davidson e Harel e la tecnica del simulated annealing, generalizzazione di Harel e Koren
  • Vincoli.

Materiale didattico di riferimento:

  • G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing &endash; Algorithms for the visualization of graphs, Prentice Hall, 1999, pp. 303-324, escluso par. 10.3.
  • C. Chen: Information Visualization beyond the horizon � 2nd Edition, Springer 2004, pp 77-80
  • PER APPROFONDIRE: Kaufmann pp. 71-86
  • PER APPROFONDIRE: D. Harel, Y. Koren. Drawing graphs with non uniform vertices. Proc. Working Conference on Advanced Visual Interfaces (AVI'02), 157--166. ACM Press, 2002.

5. Visualizzazione di superfici in 3 dimensioni

  • Il problema della triangolazione: come calcolare i punti della triangolazione; come calcolare la triangolazione, dato l'insieme dei punti; triangolaione di De Lunay e diagramma di Voronoi;
  • Modelli di illuminazione: Modelli di illuminazione locali:modello di Lambert, luce ambientale, modello di Phong, attenuazione
  • Ombreggiature: flat shading, ombreggiatura di Gourard, ombreggiatura di Phong
  • Ombre proiettate e sorgenti estese

Materiale didattico di riferimento:

  • D. Marini, M. Bertolo, A. Rizzi. Comunicazione Visiva Digitale � Fondamenti di eidomatica. Addison-Wesley, 2001, pp. 87-92, 254-259, 262-266.
  • G. Attardi, A. Bernasconi. Fondamenti di Computer Graphics, 1997. paragrafi 9.1, 9.2 e 9.4; http://medialab.di.unipi.it/web/IUM/Fondamenti/cap9.htm

6. Visualizzazione di topologie di interconnessione

  • Il modello di Thompson per il layout; vincoli dettati dalla tecnologia VLSI; cenni al layout 3D
  • Diversi layout di una stessa topologia di interconnessione (butterfly): Layout 'slanted'; Layout via layered cross product; Raffronto delle due rappresentazioni e cenni all'ottimizzazione dell'area

Materiale didattico di riferimento:

  • F. T. Leighton: Introducton to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann ed. 1992, pp. 440-442.
  • D.S. Wise: "Compact Layouts of Banyan/FFT Networks", VLSI Systems and Computations, pp.186-195, 1981, solo disegno e osservazioni su di esso.
  • G. Even, S. Even: "Embedding Interconnection Networks in Grids via the Layered Cross Product", Networks 36(2), pp. 91-95, 2000, esclusa sez. 3.3.

7. Visualizzazione di carte geografiche

  • Premessa: problemi NP-completi, riduzioni polinomiali; un algoritmo per 2-SAT
  • Il problema della etichettatura degli oggetti
  • Panoramica della complessita' di problemi di etichettatura di oggetti: etichettatura di punti e di linee
  • Alcuni algoritmi di etichettatura: etichettatura di punti, di linee, di carte geografiche
  • Il problema della determinazione delle intersezioni di segmenti: algoritmo e sua correttezza

Materiale didattico di riferimento:

  • Cormen, Leiserson, Rivest; Introduzione agli algoritmi, Jackson Libri 1995, pp.864-877, 883-885 esclusa dim. Th. Di Cook.
  • C.H. Papadimitriou: Computational complexity, Addison-Wesley Publ. Co. 1994, pp 183-187.
  • M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 247-273, esclusi par. 10.3.5, 10.3.6, 10.6.
  • M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry; Algorithms and Applications. Springer-Verlag, Heidelberg, 1997, pagg. 19-29.

8. Visualizzazione di oggetti molto grandi (infiniti)

  • Esempi di oggetti molto grandi: mappa del web, relazioni di dipendenza tra moduli software, ecc.
  • Tecnica della clusterizzazione
  • Un algoritmo per la rappresentazione di grafi clusterizzati
  • Tecnica della navigazione
  • Discussione delle problematiche collegate a queste due tecniche e loro raffronto
  • Occhio di pesce
  • Altre tecniche

Materiale didattico di riferimento:

  • P. Eades, Q.-W. Feng: Multilevel Visualization of Clustered Graphs. Proc. Graph Drawing '96, LNCS 1190, pp. 101-112, 1996 escluso approccio gerarchico all'interno della sez. 3.1.
  • C. Chen: Information Visualization beyond the horizon � 2nd Edition, Springer 2004, pp 30-32.
  • PER APPROFONDIRE: M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 193-227.
Edit | Attach | Watch | Print version | History: r14 < r13 < r12 < r11 < r10 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r14 - 2009-12-11 - TizianaCalamoneri






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback