Departamento de Computación

El estudio del problema de coloración de aristas en gráficas geométricas es reciente. Una gráfica geométrica es una gráfica dibujada (encajada) en el plano donde los vértices son puntos y las aristas son segmentos de recta entre parejas de puntos. El problema de la coloración de aristas consiste en asignar un máximo o mínimo de colores a las aristas de la gráfica, de tal forma que las aristas que son disjuntas posean colores distintos. Este número k de colores utilizado, se encuentra acotado por las condiciones que impone el llamado índice de coloración. Actualmente, los resultados existentes en la literatura para coloraciones en gráfocas bipartitas geométricas, son escasos. En esta tesis estudiamos algunos índices de coloración para gráficas geométricas. Específicamente, obtenemos cotas para los índices de coloración cromático, acromático y de Grundy; en particular, nos centramos en el estudio de los dos últimos. Diseñamos algoritmos de coloración para dar cotas inferiores para ciertas familias de gráficas, mientras que, para obtener las cotas superiores, utilizamos procesos de conteo para ciertas familias de gráficas, y buscamos encajes que requieran pocos colores para cualquier familia. Las cotas obtenidas son bastante justas, y en algunos casos son cerradas. Además, diseñamos diversas aplicaciones y experimentos computacionales, los cuales usamos como apoyo para obtener las cotas combinatorias. Así también, implementamos los algoritmos de coloración propuestos.

Abstract

The problem of coloring the edges of a geometric graph, has been studied only recently. A geometric graph is a graph drawn in the plane, such that its vertices are distinct points and its edges are straight-line segments connecting pairs of points. An edge coloring of a geometric graph is an assignment of colors to the edges of the graph, so that no two adjacent edges have the same color. There exist a collection of edge-coloring type problems, that is, problems in which the question is whether it is possible to color the edges of a given graph using k colors, and in such a way that the coloring meets some additional requirements. These additional requirements are defined by one of the (so called) coloring indexes. Currently, there are only few results about edge-coloring problems for geometric graphs. In this thesis, we study some edge-coloring problems for some families of geometric graphs. Specifically, we give upper and lower bounds for the chromatic, achromatic and Grundy indexes. For each one of these indexes, we designed coloring algorithms to provide lower bounds for some families of geometric graphs. As for the upper bounds, we used combinatorial techniques to obtain them for some families of graphs, and we searched for geometric embeddings requiring few colors for every family of graphs. The obtained bounds are quite tight and, in some cases, even closed. In addition, we designed computer applications and perform experiments which helped us to support these combinatorial bounds. We have also implemented the proposed coloring algorithms.