Inmersiones de grafos en superficies y seudosuperficies con todos los vértices en una misma cara

Description

La memoria se enmarca en la "Teoría de Inmersiones de Grafos en Superficies", presentando y resolviendo varios e interesantes problemas sobre dicho tema. Destacan especialmente los resultados referidos al estudio de los grafos peri S tanto en seudosuperficies para las que no se ... conoce su "teorema de Kuratowski", como en otras en las que se sabe que este no es finito.Se estudian las inmersiones peri sin acumulación de vértices para el caso de grafos infinitos en superficies tubulares y se dan algoritmos para obtener tanto los menores como los menores topológicos prohibidos para la peri-representabilidad en otras seudosuperficies.También se analizan los grafos no numerables que admiten inmersión en superficies con todos los vértices, en una misma cara.Ésta se divide en tres partes claramente diferenciadas: un primer capítulo de concpetos previos, una parte relativa a grafos finitos y otra que trata de grafos infinitos.El Capítulo 0 servirá para recordar algunos conceptos topológicos básicos, enunciar resultados generales y fijar una notación adecuada para trabajar con grafos peri-represntables.La primera parte se compone de 3 capítulos sobre grafos:En el primero de ellos, se plantean varios problemas de índole algorítmica y se introducen las principales dificultades comunes a casi todos los problemas de peri-represntabilidad en seudosuperficies. En concreto, se prueba la NP-completitud del problema de la peri-representabilidad en seudosuperficies y se aportan resultados sobre los grafos peri en el toro estrangulado, que abren la posibilidad de obtener menores peri prohibidos en dicha seudosupercies. El segundo, se dedica al estudio de los grafos que admiten inmersiones peri en seudosuperficies formadas por esferas pegadas por puntos de modo que cada esfera tiene 2 puntos singulares. Según se explica al principio del capítulo, cualquier grafo admite una inmersión peri en una seudosuperficie de este tipo, por lo que no parece una familia excesivamente restringida. En particular, se consiguen listas finitas de menores periprohibidos en seudosuperfices en las que las listas de menores topológicos prohibidos son infinitas y se obtienen varios resultados más que pueden llegar a sorprender por no resultar habituales en las inmersiones de grafos.El último capítulo de la primera parte, trata de los grafos peri en otras seudosuperfices que se obtienen mediante la contracción a puntos de curvas de superficies compactas (tanto orientables como no orientables). En cada tipo de seudosuperficie se propone una forma distinta de caracterización, relacionando dichos grafos peri con otras familias de grafos o con los que se obtienen de la aplicación de ciertos algoritmos que se describen.La segunda parte, que versa sobre las inmersiones peri de grafos infinitos, se divide en 2 capítulos:En el Capítulo 4 se trabaja con grafos numerables, a los que se exige que posean inmersiones peri sin acumulación de vértices ni de aristas. Las superficies no compactas que se utilizan son tubulares con una cantidad finita de finales. Se parte de la coloración de finales como procedimiento para distinguir los finales tanto en grafos como en las superficies, gracia a esta forma de proceder, se consigue generalizar la caracterización de los grafos p-periplanos a casos como el del cilindro y se resuelve el problema de la banda de Möbius. En el último capítulo se explican las diferencias entre los resultados de capítulos anteriores y los que se obtienen para grafos no numerables. En algunos de ellos se enuncian explícitamente los teoremas de caracterización de los grafos peri. En otros, como sucede a lo largo de de toda la memoria, se proponen formas de actuar ante los nuevos problemas que se abren a la investigación en Teoría de Grafos.Al final de la memoria, a modo de apéndice, se describen los algoritmos aplicados para obtener los menores peri prohibidos y los menores topológicos peri prohibidos en la banda de Möbius a partir de los menores peri-proyectivos prohibidos.

Additional details