Problemas de conexiones ortogonales

Abstract

El área de investigación sobre dibujos de grafos constituye una importante conexión entre diversos campos de la Matemática, tales como la algorítmica, la geometría computacional y la teoria topológica de grafos. Dentro de ella, el estudio de las inmersiones ortogonales ocupa un lugar importante por su aplicación a diversos problemas: dise&nti lde;o de circuitos VLSI, donde da lugar a diversos problemas de optimización, creación de diagramas de flujo y organigramas, diseño de bases de datos en ingenieria del software y problemas de etiquetado de mapas y otras aplicaciones en sistemas de información geográfica. Motivados por el trabajo de Raghavan et al. sobre el conocido problema EOSP (emparejamiento ortogonal simple en el plano), nos planteamos, en primer lugar, la extensión de este problema a otras superficies. Este tema constituye la primera parte de la memoria que se presenta. Se estudian en ella la complejidad computacional de los problemas de emparejamiento ortogonal simple (EOS), mostrando, en primer lugar, el comportamiento polinomial del problema cuando únicamente existen dos posibles caminos entre cada pareja de puntos. Sin embargo, el problema con un mayor numero de caminos, asi como el problema general resultan ser NP-completos y el problema de optimización asociado a este último es, por lo tanto, NP-duro. Otra ampliación necesaria del problema EOSP es estudiar, no las conexiones entre parejas, sino entre grupos de puntos, usando inmersiones ortogonales de grafos y permitiendo un numero de codos superior a uno por cada inmersión. Este estudio, realizado en el pleno, ocupa la segunda parte de la memoria. En ella se clasifican los problemas de conexión ortogonal plana según su complejidad computacional. En primer lugar, caracterizamos una serie de problemas resolubles en tiempo polinomial, mediante reducción a problemas de logica simbolica o sumando técnicas de geometria computacional. A continuación, se estudia una familia de problemas directamente relacionados con problemas de etiquetado, obteniendo una caracterización completa de la complejidad computacional del problema del trazado sin cruces de triangulos ortogonales en el plano en función del numero de codos, incluyendo la condicion de NP-completitud. Finalmente, se dan condiciones necesarias para que el problema de conexión ortogonal plana sea NP-completo, estudiando asimismo diversos problemas que no verifican alguna de estas condiciones, pero que también tienen complejidad NP.