Título:  Sobre la thinness en un grafo
Directora: Flavia Bonomo
Jurados: Luciano Grippo y Hernán Melgratti

Resumen:
La thinness de un grafo, denida inicialmente en 2007, es un invariante que generaliza a los grafos de intervalos. Todo grafo tiene un valor numerico de thinness y los grafos con thinness 1 coinciden con los grafos de intervalos.
Un grafo es k-thin si sus vértices pueden ordenarse de manera que exista una partición de los vertices en k clases cumpliendo que para cada tripla de vertices r < s < t si r y s pertenecen a la misma clase y existe una arista entre r y t, entonces existe una arista entre s y t. La thinness es el menor valor de k tal que el grafo sea k-thin.
En este trabajo denimos un modelo de intersección para los grafos con thinness y thinness propia menor o igual a 2 restringiendo los grafos con boxicity 2. Se caracterizan los grafos k-thin y k-thin propios utilizando propiedades de la matriz de adyacencia. Se acota la thinness en relacion al bandwidth de un grafo y se hace un resumen de las relaciones conocidas.
Se calcula la thinness utilizando SAT Module Theory (SMT), tanto para determinar si vale la propiedad k-thin como para obtener el valor de la thinness mediante optimización. Se evalua la perfomance sobre familias de grafos con los resolvedores Z3 Theorem Solver y OptiMathSat. Adicionalmente se utilizan las mismas tecnicas para calcular una representación como una intersección de rectángulos en el plano.

Palabras clave: Grafo, Thinness, Intervalo, Boxicity, Intersección, Bandwidth, SMT, Z3