-* Titolo:* Domination Number of Planar Graphs
-* Breve descrizione dell'attivit� da svolgere:* La tesina � volta allo studio del seguente problema.

Dato un grafo (V,E), un sottoinsieme S di V  � detto/ dominating set /se ogni vertice di V o appartiene a S o � adiacente ad un vertice di S.
Il problema consiste nel determinare quanto vertici deve contenere, al pi�, un dominating set per un qualsiasi grafo planare.

L'attivit� da svolgere consiste nella ricerca bibliografica sul'argomento, la lettura e comprensione di tale bibliografia e, eventualmente, la proposta di un metodo per calcolare il dominating set di grafi planari.

*- Crediti previsti*:  5
*- Eventuali vincoli temporali: *nessuno
*- Riferimento: Fabrizio Frati


---


*-Titolo:* Rooted Trees into Point Sets
*-Breve descrizione dell'attivit� da svolgere:* La tesina � volta allo studio del seguente problema.

E' dato un insieme T={T1,T2,...,Tk} di alberi radicati, per un totale di n vertici. E' dato un insieme S di n punti nel piano, di cui k punti {v1,v2,...,vk} corrispondono alle radici di questi alberi. E' sempre possibile disegnare gli alberi con i vertici sui punti di S (1 vertice per punto) in maniera tale che
   ogni radice � sul punto corrispondente
   ogni arco sia rappresentato da un segmento
   non ci sono intersezioni fra archi

L'attivit� da svolgere consiste nella ricerca bibliografica sul'argomento, la lettura e comprensione di tale bibliografia e, eventualmente, la proposta di un metodo per disegnare alberi su insiemi di punti.

*- Crediti previsti:*  5
*- Eventuali vincoli temporali: *nessuno
*- Riferimento: Fabrizio Frati


---


Titolo:
 	Confronto tra librerie di graph drawing

Breve descrizione dell'attivit�  da svolgere:
	La tesina consiste nel confrontare due o pi�' librerie di graph drawing, individuando le eventuali similitudini e differenze nelle funzionalit� .
Il confronto pu�" prevedere anche un confronto sperimentale sulle prestazioni delle librerie con grafi di grandi dimensioni. E' richiesta la conoscenza del linguaggio C++

Crediti previsti: 5

Eventuali vincoli temporali: nessuno