TESELACIONES Y GRAFOS DE INTERSECCION

En numerosas aplicaciones se utilizan representaciones gráficas para esquematizar información. El objetivo de estas representaciones es simplificar la estructura de los datos en un espacio relativamente pequeño. Por lo general un dibujo vale más que mil palabras, siempre que el dibujo sea claro y legible. El dibujo de grafos es una joven área de investigación que plantea justamente ese problema: construir representaciones geométricas de grafos esquematizando la información de la manera más sencilla posible. En esta memoria estudiamos tres representaciones de grafos que constituyen particiones ortogonales del plano o de otras superficies y tienen aplicación práctica en diversos problemas tales como el diseño de circuitos eléctricos, diseño arquitectónico o diseño de bases de datos. Los problemas que nos planteamos consisten en determinar qué grafos admiten una representación en la que sus vértices están asociados a objetos geométricos (segmentos o rectángulos) y sus aristas son relaciones entre esos objetos (de visibilidad o de adyacencia). El problema de determinar qué grafos admiten este tipo de representación y, caso de que la admitan encontrarla, está resuelto para grafos en el plano. Surge la necesidad de estudiar otras superficies además del plano, ya que la mayoría de los problemas prácticos que se plantean, sobre todo los relacionados con la planificación de movimientos en robots, no se encuentran en general en el plano, sino que describen una variedad algebraica inmersa en el espacio. Por esta razón, parece interesante el estudio en otras superficies no planas. Se han escogido, para la generalziación al caso no plano, las superficies del cilindro y el toro, utilizando en ambos casos particiones ortogonales de ambas superficies.