Raffigurazione di un grafo

La raffigurazione dei grafi, o tracciamento dei grafi, è una disciplina che si colloca tra la teoria dei grafi e l'informatica, che si occupa della rappresentazione dei grafi in due o tre dimensioni. Questa attività è motivata da importanti applicazioni della teoria dei grafi, come la progettazione di circuiti VLSI, la cartografia, la bioinformatica, l'analisi delle reti sociali. Essa richiede l'uso di nozioni di geometria e topologia e lo sviluppo di algoritmi e di impegnativi sistemi software.

Teoria

Consideriamo una superficie S nello spazio tridimensionale. In particolare S potrebbe essere un piano, una sfera o un toro. In teoria dei grafi si dice raffigurazione di un grafo G su una superficie S una figura tracciata su S in cui ogni nodo di G è rappresentato da un punto diverso di S (punto-nodo) mentre ogni vertice {p,q} di G è rappresentato da una curva (curva-spigolo) tendenzialmente regolare che ha le estremità nei punti-nodi corrispondenti a p e q e che non tocca nessun altro punto-nodo.

Quando la superficie S è un piano si parla di raffigurazione piana del grafo.

Due raffigurazioni di un grafo sopra una superficie si dicono topologicamente equivalenti se si possono trasformare l'una nell'altra mediante una deformazione continua. Una tale deformazione non si può far attraversare una curva-spigolo da un punto-nodo.

Tra le raffigurazioni di un grafo si distinguono quelle nelle quali non si hanno spigoli che si intersecano: queste vengono chiamate raffigurazioni planari. In particolare, si distinguono le raffigurazioni piane planari.

Esistono grafi che non possiedono raffigurazioni piane planari, quali, ad esempio, i grafi di Kuratowski. Si possono ottenere raffigurazioni planari per ogni grafo a patto di complicare la superficie di immersione: da un punto di vista intuitivo, si tratta di aggiungere a tale superficie un sufficiente numero di manici.

Criteri sul disegno di grafi

Grafi planari

grafo planare raffigurato con un disegno senza intersezioni di archi

Si definisce planare un grafo che può essere disegnato sul piano in modo che le connessioni tra i nodi possano essere rappresentate da segmenti che non si intersecano. Un disegno senza intersezioni tra archi rende il grafo molto comprensibile ad occhio umano

Algoritmi

Algoritmi Force directed

Gli algoritmi force-directed, cioè orientati alle forze, sono una classe di algoritmi per disegnare grafi. Un algoritmo di questo tipo considera il disegno del grafo come un sistema fisico, in cui sono in gioco forze sui nodi. Ad esempio l'algoritmo di Eades (1984) prevede che vi siano forze attrattive tra i nodi adiacenti, come avviene in una molla. Queste forze fanno sì che i nodi adiacenti si avvicinino nel disegno finale. Allo stesso tempo l'algoritmo di Eades considera forze repulsive tra i nodi non adiacenti, queste forze fanno sì che due nodi non adiacenti tendano ad allontanarsi nel disegno finale. L'energia totale del sistema fisico diminuira' se i nodi adiacenti sono vicini e i nodi non adiacenti sono lontani. Un disegno comprensibile e gradevole è correlato ad un sistema fisico con bassa energia.

Bibliografia

• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999.
• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis, Algorithms for Drawing Graphs: an Annotated Bibliography, in Computational Geometry: Theory and Applications, 4, pp. 235-282 (1994).
• Isabel F. Cruz, Roberto Tamassia, Graph Drawing Tutorial

Voci correlate

• Grafo planare

Collegamenti esterni

I siti web sottoindicati sono particolarmente degni di nota.

• graphdrawing.org, sito ufficiale del "Graph Drawing Steering Committee", il comitato che organizza l'annuale International Symposium on Graph Drawing. Include una introduzione del linguaggio per la descrizione dei grafi graphml, esempi di descrizioni di grafi specifici e collegamenti a molte altre risorse per la raffigurazione dei grafi.
• Graph drawing e-print archive raccoglie informazioni sugli articoli presentati a tutti i simposi sul Graph Drawing.
• pagina dell'Open Directory Project contenente molti altri link concernenti il Graph drawing
• sito web dedicato a Chisio, semplice strumento per la visualizzazione, open source e di origine accademica.