Se llevará a cabo investigación básica sobre gráficas geométricas._x000D_ _x000D_ Los recursos que se solicitan al fondo PAPIIT son para la compra de equipo de cómputo de alto desempeño complementario para el desarollo del proyecto SEP-Conacyt número 168277, titulado "gráficas geométricas", cuyo responsable es el solicitante de este proyecto. _x000D_ _x000D_ Usaremos el equipo de cómputo solicitado para poder buscar programáticamente ejemplos y contraejemplos que nos puedan guiar en la formulación de soluciones a nuestras preguntas. La mayoría de los problemas que estudiemos resultan computacionalmente difíciles (son problemas NP-Completos), y para poder explorar estos problemas el uso de cómputo de alto desempeño es muy importante. _x000D_ _x000D_ Anteriormente hemos empleado equipo de cómputo para dirigir nuestra investigación: usando un cluster de 8 computadoras, F. Zaragoza encontró resultados parciales a nuestra investigación conjunta. En particular encontró que toda gráfica 4-coloreable de hasta 13 vértices tiene un dibujo primitivo plano pequeño. Este es un resultado parcial muy importante para determina si toda gráfica 4-colorable tiene un dibujo primitivo plano._x000D_ _x000D_ En la sección de antecedentes se describen las gráficas geométricas y se mencionan resultados previos del proponente respecto a estos objetos._x000D_ _x000D_ En la metodología se proponen dos problemas específicos a estudiar, como ilustración del tipo de problemas que estudiaremos. También se mencionan los resultados previos de ambos problemas. _x000D_ El proponente es coautor de los resultados previos más importantes del primero de estos dos problemas: dibujos primitivos de gráficas. De este problema se habla en la primera parte. _x000D_ En la segunda parte se habla sobre el problema de Hamiltonicidad en gráficas geométricas. La hamiltonicidad es una propiedad muy importante de cualquier gráfica, en un sentido práctico._x000D_ _x000D_ Es importante aclarar que trabajaremos, además de en estos problemas, en muchos otros más que tengan que ver con graficas geométricas en particular, y con geometría computacional y combinatoria en general._x000D_ _x000D_ Puesto que las gráficas geométricas aparecen de manera natural en muchas áreas de computación, los resultados que se obtendran, además de ser valiosos en el sentido de investigación básica, tienen el potencial de servir como fundamentos para el desarrollo y mejora de tecnologías concretas de computo. Algunas de estas tecnologías son Diseño de microprocesadores (VLSI), Sistemas de información geográfica (GIS) y Diseño Asistido por computadora (CAD), por mencionar sólo algunas._x000D_ _x000D_ _x000D_

Utilizando cómputo de alto desempeño se experimentará con objetos combinatorios que guien la búsqueda de resultados básicos de geometría combinatoria y computacional._x000D_ _x000D_ Con esta experimentacion se obtendrán ejemplos y contraejemplos a problemas abiertos de investigación. Estos serán muy útiles en la búsqueda de resultados algorítmicos y combinatorios en gráficas geométricas. Objetos matemáticos que de manera natural aparecen fácilmente en las ciencias de la computación y en matemáticas. _x000D_ _x000D_ Colaborando con otros investigadores, e involucrando alumnos de licenciatura y maestría, se espera continuar obteniendo resultados de investigación básica, que a largo plazo puedan permitir la mejora y la creación de tecnologías de cómputo concretas, incluyendo el diseño de circuitos electrónicos con gran escala de integración (VLSI), redes de computadoras, diseño asistido por computadora, sistemas de información geográfica y algunas otras áreas de la computación que inciden directa o indirectamente en la vida de millones de personas._x000D_ _x000D_ Los resultados obtenidos, tanto experimentales como básicos, serán comunicados a la comunidad científicas mediante publicaciones en revistas indizadas y mediante exposiciones en congresos especializados. _x000D_ _x000D_ _x000D_ _x000D_ _x000D_