Grafo trapezoidal
# 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.

## Definiciones y caracterizaciones

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_1$ … $P_d$ tal que P = $P_1∩…∩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.

## Aplicaciones

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

### Representación trapezoidal

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

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. Una representación en caja equivalente al grafo de la Figura 1 se muestra en la Figura 3.

### Grafos de bitolerancia(grafos bitolerantes)

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_1(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_1(y)$ y el centro de $I_x$ es menos que el centro de $I_y.$ En 1993 Langley demostró que los grafos bitolerantes acotados son equivalentes a la clase de grafos trapezoidales.

## Relación con otras familias de grafos

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

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

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

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)$. 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

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_2$ inducido). 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.

