Raffigurazione di un grafo

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica sorgente]

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.

Bibliografia[modifica | modifica sorgente]

  • 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[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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.
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica