Grafo trapezoidal

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.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.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.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.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.Usando la noción de orden dominante(En RK, x se dice dominada por y, y se denota mediante, x < y, si xi es menor que yi 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.[3]​ En 1993 Langley demostró que los grafos bitolerantes acotados son equivalentes a la clase de grafos trapezoidales.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.para el problema del clique de costo máximo.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 vectorUsando á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 dePara esta clase más amplia de grafos, los problemas del mayor conjunto independiente y el clique de cubrimiento mínimo pueden ser resueltos en ordenpara 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 ordenpara 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.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 ordenque da como resultado, algoritmos de ordenno existe, se prueba para ver si el orden arrojado porEl algoritmo más rápido para reconocer un orden trapezoidal fue propuesto por McConell y Spinrad en 1994, con una complejidad temporal de orden[6]​ Usando separación de vértices, el problema de reconocer un grafo trapezoidal fue mostrado por Mertzios y Corneil que triunfaba en ordenEste proceso involucra el aumento de un grafo, y luego transformar el grafo aumentado remplazando cada uno de los vértices del grafo original por un nuevo par de vértices.