Inmersiones ortogonales de grafos en superficies no planas

Resumen

El área de investigación sobre dibujos de grafos (graph drawing) se ha convertido en un campo extensamente estudiado, constituyendo una interesante conexión entre la computación y la teoría de grafos. Dentro de ella, la representación ortogonal de grafos ocupa un lugar importante por su aplicación al diseño de circuitos VLSI, dando lugar a diversos problemas de optimización. Esta memoria está dedicada al estudio de las inmersiones ortogonales de grafos en superficies, con el objeto de minimizar el número de codos. Motivados por el trabajo de Tamassia realizado en el plano, nos planteamos el problema de caracterizar la inmersión ortogonal cilíndrica que presenta el mínimo número de codos, entre todas las equivalentes a las de partida. Comenzamos realizando la caracterización de la asignación ortogonal óptima, concepto que recoge la información de los ángulos y codos del trazado, obteniéndola en tiempo polinomial. En el plano, los conceptos de asignación ortogonal e inmersión en la malla son equivalentes. Sin embargo, en el cilindro la situación es muy distinta, por lo que realizamos un estudio detallado de la relación entre ambas estructuras, destacando las diferencias con respecto al plano. Igualmente, diseñamos algoritmos efectivos que proporcionan inmersiones ortogonales cilíndricas, de forma que el número total de codos obtenido constituye una buena aproximación del valor óptimo, guiados por dos enfoques, uno global en el grafo y otro local en cada arista. Desde un punto de vista práctico, es necesario el estudio de inmersiones ortogonales de grafos en superficies. Este hecho nos conduce al planteamiento de dos importantes problemas en este ámbito, demostrando su naturaleza NP-completa: por una parte, dada una inmersión en una superficie, decidir si admite una inmersión ortogonal sin codos esencialmente equivalente; y por otra parte, encontrar una superficie en la que un grafo dado admita una inmersión ortogonal sin codos. Dada la intratabilidad computacional de estos problemas, para obtener soluciones óptimas, presentamos algorítmos lineales de construcción de inmersiones ortogonales en superficies arbitrarias, que constituyen buenas aproximaciones a la solución óptima.