Grafo trapezoidal

En teoría de grafos, los grafos trapezoidales son grafos de intersección de trapezoides entre dos líneas horizontales. Son una clase de grafos co-comparables que contienen como subclases a los grafos de permutaciónes y a los Grafos de intervalos. Se dice que tenemos un grafo trapezoidal, si existe un conjunto de trapezoides que se correspondan a los vértices del grafo que cumplan que dos vértices están unidos por una arista si y solo si los trapezoides correspondientes a los mismos se intersecan. Los grafos trapezoidales fueron introducidos por Dagan, Golumbic, y Pinter en 1968. Existen algoritmos de ${O}(n\log n)$ para calcular su número cromático, su Conjunto independiente con costo(conjunto independiente ponderado), cobertura de clique(número de clique) y clique de costo máximo.

Figura 2: Representación trapezoidal de un grafo G.

Definiciones y caracterizaciones[editar]

Dado un canal, un par de líneas horizontales, un trapezoide entre estas líneas se define por dos puntos de la línea superior y dos de la inferior. Un grafo se dice trapezoidal, si existe un conjunto de trapezoides que se correspondan a los vértices del grafo que cumplan que dos vértices están unidos por una arista si y solo si los trapezoides correspondientes a los mismos se intersecan. La dimensión del orden del intervalo de un conjunto parcialmente ordenado, $P=(X,<)$ , es el mínimo d de los órdenes de intervalo P₁ … P_d tal que P = P₁∩…∩P_d. El grafo de incomparabilidad(grafo incomparable) de un conjunto parcialmente ordenado $P=(X,<)$ , es el grafo no dirigido $G=(X,E)$ , donde x es adyacente a y en G si y solo si x y y son incomparables en P. Un grafo no dirigido es un grafo trapezoidal, si y solo si, es el grafo de incomparabilidad(grafo incomparable) de un orden parcial teniendo un orden de intervalo de como máximo 2.^[1]

Aplicaciones[editar]

Los problemas de hallar el clique de tamaño máximo y de colorear grafos trapezoidales están conectados a los problemas de ruteo de canales en diseño VLSI. Dadas algunas terminales etiquetadas en los lados superior e inferior de un canal con dos lados, las terminales con una misma etiqueta serán conectadas a una red común. Esta red puede ser representada mediante un trapezoide que contenga a los terminales a la izquierda y derecha con su etiqueta común. Las redes pueden ser enrutadas sin intersección, si y solo si, los trapezoides no se intersecan. Por tanto el número de capas necesarias para enrutar la red sin intersecciones es igual al número cromático del grafo.

Representaciones equivalentes[editar]

Representación trapezoidal[editar]

Los trapezoides pueden ser usados para representar un grafo trapezoidal usando la definición de un grafo trapezoidal como tal. Un grafo trapezoidal y su correspondiente representación como trapezoide, puede verse en las figuras 1 y 2.

Representación en caja[editar]

Rectángulos dominantes o representación en caja, mapea los puntos de la línea inferior de la representación trapezoidal, haciéndolo corresponder con el eje de las x o dominio y la línea superior con el eje de las y o imagen del plano euclidiano. Cada trapezoide se corresponde a una caja paralela a los ejes del plano. Usando la noción de orden dominante(En R^K, x se dice dominada por y, y se denota mediante, x < y, si x_i es menor que y_i para i = 1, …, k), decimos que una caja b domina a una caja b’ si la esquina inferior de b domina a la esquina superior de b’. Además, si una de las dos cajas domina a la otra decimos que son comparables. De otro modo son incomparables. Luego, dos trapezoides son exactamente disjuntos si sus cajas correspondientes son comparables. La representación de caja es útil porque el orden dominante que se le asocia permite el uso de algoritmos de barrido de línea.^[2] Una representación en caja equivalente al grafo de la Figura 1 se muestra en la Figura 3.

Grafos de bitolerancia(grafos bitolerantes)[editar]

Los grafos de bitolerancia son grafos incomparables de un orden bitolerante. Un orden, se dice bitolerante si y solo si hay intervalos I_x y números reales t₁(x) y t_r(x) asignado a cada vértice x de modo que ambosx < y si y solo si el solapamiento de I_x y I_y es menos que ambos t_r(x) y t₁(y) y el centro de I_x es menos que el centro de I_y.^[3] En 1993 Langley demostró que los grafos bitolerantes acotados son equivalentes a la clase de grafos trapezoidales.^[4]

Relación con otras familias de grafos[editar]

La clase de grafos trapezoidales propiamente dicha contiene la unión de grafos de intervalo y grafos de permutaciones y es equivalente a los grafos de incomparabilidad o conjuntos parcialmente ordenados con un orden de dimensión de intervalos de a lo sumo 2. Los grafos de permutación pueden ser vistos como un caso especial de los grafos trapezoidales cuando estos tienen área igual a 0. Esto ocurre cuando ambos puntos del trapezoide en el canal superior están en la misma posición y los puntos del canal inferior están en la misma posición.

Como todos los grafos incomparables los grafos trapezoidales son perfectos.

Grafos trapezoidales circulares[editar]

Los grafos circulares trapezoidales, son una clase de grafos propuesta por Felsner en 1993. Son una superclase de la clase de grafos trapezoidales, y contienen también los grafos circulares y grafos arco circular. Un círculo trapezoidal es la región en un círculo que se encuentra entre dos cuerdas que no se cruzan y un grafo circular trapezoidal es el grafo de intersección de las familias de círculos trapezoidales en un círculo común. Un grafo circular trapezoidal y su correspondiente representación circular trapezoidal puede ser vista en la Figura 4. Existe un algoritmo de orden $O(n^{2})$ para el problema de hallar el conjunto independiente de costo máximo y uno de orden ${O}(n^{2}\log n)$ para el problema del clique de costo máximo.

Grafos k-Trapezoidales[editar]

Los grafos k-Trapezoidales son una extensión de los grafos trapezoidales a órdenes de dimensión mayores. Fueron propuestos por primera vez por Felsner, y se fundamentan en la definición de cajas dominantes extendiéndolas a mayores dimensiones en donde un punto x es representado mediante un vector $(x_{1},\ldots ,x_{k})$ . Usando árboles de rango (k − 1)-dimensional para guardar y consultar coordenadas, los algoritmos de Felsner para número cromático, clique máximo y máximo conjunto independiente pueden ser aplicados a los grafos k-Trapezoidales en un orden de ${O}(n\log ^{k-1}n)$ .

Algoritmos[editar]

Los algoritmos para grafos trapezoidales deben ser comparados con algoritmos para grafos co-comparables en general. Para esta clase más amplia de grafos, los problemas del mayor conjunto independiente y el clique de cubrimiento mínimo pueden ser resueltos en orden ${O}(n^{2}\log n)$ .^[5] Dagan propuso un algoritmo en orden ${O}(nk)$ para colorear grafos trapezoidales, donde n es el número de nodos y k es el número cromático del grafo. Más tarde, usando la representación en caja de los grafos trapezoidales, Felsner publicó algoritmos de orden ${O}(n\log n)$ para los problemas del número cromático, conjunto independiente ponderado, cubrimiento de clique, y clique de costo máximo. Todos estos algoritmos tienen una complejidad espacial de orden ${O}(n)$ .Estos algoritmos descansan en la dominancia asociada en la representación en caja que permite el uso de algoritmos de pasada o barrido. Felsner propone el uso de árboles balanceados que pueden hacer la inserción, eliminación y búsqueda en orden ${O}(\log n)$ que da como resultado, algoritmos de orden ${O}(n\log n)$ .

Reconocimiento[editar]

Para determinar si un grafo ${G}$ es trapezoidal, se busca una orientación transitiva ${F}$ en el complemento de ${G}$ . Como los grafos trapezoidales son un subconjunto de los grafos co-comparables, si un grafo ${G}$ es trapezoidal, su complemento ${G'}$ debe ser un grafo de comparabilidad o comparable. Si no existe una orientación transitiva ${F}$ del complemento ${G'}$ , ${G}$ no es un grafo trapezoidal. Si ${F}$ no existe, se prueba para ver si el orden arrojado por ${F}$ es un orden trapezoidal. El algoritmo más rápido para reconocer un orden trapezoidal fue propuesto por McConell y Spinrad en 1994, con una complejidad temporal de orden $O(n^{2})$ . El proceso reduce la pregunta de dimensión del intervalo 2 a un problema de cubrimiento de un grafo bipartito por grafos encadenados(grafos sin 2K₂ inducido).^[6] Usando separación de vértices, el problema de reconocer un grafo trapezoidal fue mostrado por Mertzios y Corneil que triunfaba en orden $O(n(n+m))$ , donde $m$ denota el número de aristas. Este proceso involucra el aumento de un grafo ${G}$ , y luego transformar el grafo aumentado remplazando cada uno de los vértices del grafo original por un nuevo par de vértices. Este grafo “partido” es un grafo de permutación con propiedades especiales si y solo si ${G}$ es un grafo trapezoidal.^[7]

Notas[editar]

↑ Ido Dagan, Martin Charles Golumbic, and Ron Yair Pinter. Trapezoid graphs and their coloring. Discrete Appl. Math., 35–46, 1988.
↑ Stefan Felsner, Rudolf Muller, and Lorenz Wernisch. Trapezoid graphs and generalizations, geometry and algorithms. In Algorithm theory—SWAT ’94 (Aarhus, 1994), volume 824 of Lecture Notes in Comput. Sci., pages 143–154. Springer, Berlin, 1994.
↑ Kenneth P. Bogart, Garth Isaak. Proper and unit bitolerance orders and graphs. Discrete Mathematics 181(1–3): 37–51 (1998).
↑ Martin Charles Golumbic and Irith B.-A. Hartman, eds., Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications, Springer-Verlag, New York, 2005
↑ R. McConnel and J. Spinrad, Linear-time modular decomposition and efficient transitive orientation of undirected graphs, Proc. 5. Ann. Symp. on Discr. Alg. (1994).
↑ Golumbic, Martin Charles., and Ann N. Trenk. Tolerance Graphs. Cambridge [u.a.: Cambridge Univ., 2004.
↑ G. B. Mertzios and D. G. Corneil. Vertex splitting and the recognition of trapezoid graphs. Discrete Applied Mathematics, 159(11), pages 1131-1147, 2011.

Referencias[editar]

Golumbic, Martin Charles (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press. ISBN 0-444-51530-5. Archivado desde el original el 22 de mayo de 2010. Consultado el 8 de diciembre de 2013. Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.

Datos: Q7835582

[1] Ido Dagan, Martin Charles Golumbic, and Ron Yair Pinter. Trapezoid graphs and their coloring. Discrete Appl. Math., 35–46, 1988.

[2] Stefan Felsner, Rudolf Muller, and Lorenz Wernisch. Trapezoid graphs and generalizations, geometry and algorithms. In Algorithm theory—SWAT ’94 (Aarhus, 1994), volume 824 of Lecture Notes in Comput. Sci., pages 143–154. Springer, Berlin, 1994.

[3] Kenneth P. Bogart, Garth Isaak. Proper and unit bitolerance orders and graphs. Discrete Mathematics 181(1–3): 37–51 (1998).

[4] Martin Charles Golumbic and Irith B.-A. Hartman, eds., Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications, Springer-Verlag, New York, 2005

[5] R. McConnel and J. Spinrad, Linear-time modular decomposition and efficient transitive orientation of undirected graphs, Proc. 5. Ann. Symp. on Discr. Alg. (1994).

[6] Golumbic, Martin Charles., and Ann N. Trenk. Tolerance Graphs. Cambridge [u.a.: Cambridge Univ., 2004.

[7] G. B. Mertzios and D. G. Corneil. Vertex splitting and the recognition of trapezoid graphs. Discrete Applied Mathematics, 159(11), pages 1131-1147, 2011.

[1]

[2]

[3]

[4]

[5]

[6]

[7]