Defensa Tesis Doctorado Francisco Soulignac

Título: Sobre grafos arco-circulares propios y Helly.

Un modelo arco-circular es un par $\M = (C, \A)$ donde $C$ es un círculo y $\A$ es una familia de arcos de $C$. Si ningún arco se encuentra contenido en otro arco entonces decimos que $\M$ es propio, mientras que si $\A$ satisface la propiedad de Helly entonces decimos que $\M$ es Helly. Un grafo $G$ es arco-circular si es el grafo de intersección de los arcos de un modelo arco-circular $\M$. Si además $\M$ es propio (resp. Helly) entonces decimos que $G$ es un grafo arco-circular propio (resp. Helly). Los grafos arco-circulares y sus subclases son estudiados con especial atención desde fines de 1960, y al día de hoy la literatura al respecto es muy vasta. Esto se debe a la gran cantidad de aplicaciones que poseen en áreas tan diversas como las bases de datos, la genética, la arqueología, la psicología, la economía, etc., y a las propiedades de su estructura combinatoria. El problema de reconocimiento de grafos arco-circulares, y de varias de sus subclases, puede ser resuelto en tiempo lineal. Más aún, un modelo arco-circular puede ser generado en tiempo lineal. En esta tesis estudiamos la clase de grafos arco-circulares desde una perspectiva estructural y algorítmica, concentrándonos principalmente en las subclases de grafos arco-circulares propios y Helly.