Raffigurazione di un grafo

Da Wikipedia, l'enciclopedia libera.

La raffigurazione dei grafi o tracciamento dei grafi è un'attività che si colloca tra la teoria dei grafi e l'informatica e 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 e l'analisi delle reti sociali. Essa richiede di servirsi anche di nozioni di geometria e topologia e richiede lo sviluppo di algoritmi e di sistemi software impegnativi.

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 la quale presenta per ogni nodo di G un punto diverso di S (punto-nodo) e per ogni vertice {p,q} di G presenta 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.

Una raffigurazione in un piano si dice 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. Osserviamo che con 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, ad es. i grafi di Kuratowski. Si possono ottenere raffigurazioni planari per ogni grafo complicando la superficie di immersione: intuitivamente 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. Computational Geometry: Theory and Applications 4:235-282 (1994). http://www.cs.brown.edu/people/rt/gd.html
  • Isabel F. Cruz, Roberto Tamassia. Graph Drawing Tutorial. http://www.cs.brown.edu/people/rt/gd.html

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
  • [1], sito web dedicato a Chisio, uno strumento per la visualizzazione di facile uso, open-source e di origine accademica.
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica