dibujo de dominancia
El dibujo de dominancia es un estilo de dibujo de gráficos acíclicos dirigidos que hace que las relaciones de alcance entre vértices sean visualmente evidentes. En el dibujo de dominancia, los vértices se colocan en distintos puntos del plano euclidiano y se puede alcanzar un vértice v desde otro vértice u si y solo si ambas coordenadas cartesianas de v son mayores o iguales que las coordenadas de u . Los bordes de un dibujo de dominancia se pueden dibujar como segmentos de línea recta o, en algunos casos, como cadenas poligonales . [1]
Todo grafo st -planar transitivamente reducido , un grafo plano acíclico dirigido con una sola fuente y un solo sumidero, ambos en la cara exterior de alguna incrustación del gráfico, tiene un dibujo de dominancia. El algoritmo de izquierda a derecha para encontrar estos dibujos establece la coordenada x de cada vértice para que sea su posición en un orden de búsqueda en profundidad del gráfico, comenzando con s y priorizando los bordes en orden de derecha a izquierda, y al establecer el ycoordenada a obtener de la misma manera pero priorizando los bordes en orden de izquierda a derecha. Los algoritmos típicos de dibujo de dominancia incluyen otra fase de compactación después de esta asignación de coordenadas, desplazando los vértices hacia abajo y hacia la izquierda tanto como sea posible mientras se conservan las propiedades de un dibujo de dominancia. El dibujo resultante se encuentra dentro de una cuadrícula de enteros n × n y muestra muchas de las simetrías de la incrustación topológica subyacente. Este dibujo, y más generalmente cada dibujo de dominancia de un grafo st - planar transitivamente reducido, es necesariamente plano, con bordes de línea recta. [1] [2]
Para gráficos st -planares que no se reducen transitivamente, se puede obtener un gráfico reducido transitivamente equivalente subdividiendo cada borde. Sin embargo, un dibujo en línea recta del gráfico reducido transitivamente resultante formará un dibujo del gráfico original en el que algunos bordes tienen curvas , en los vértices ficticios introducidos por la subdivisión. [1] [2] Un dibujo de dominancia plana no es necesariamente un dibujo plano hacia arriba , porque algunos bordes pueden ser horizontales, pero girarlo 45 ° necesariamente da un dibujo plano hacia arriba. [1] En una comparación con otros métodos para dibujar gráficos acíclicos dirigidos, se encontró que el algoritmo de izquierda a derecha (junto con un paso de preprocesamiento de planarización) funciona bien en términos del área de los dibujos que produce, el número de curvas y la relación de aspecto . del dibujo, pero peor en la longitud total del borde. [3]
Un gráfico acíclico dirigido (independientemente de la planaridad) tiene un dibujo de dominancia si y solo si el conjunto parcialmente ordenado de sus vértices, ordenado por alcanzabilidad, tiene una dimensión de orden dos. El dibujo de dominancia (girado) de un gráfico acíclico dirigido transitivamente reducido puede usarse como un diagrama de Hasse del orden parcial correspondiente. [4]
Dado un dibujo de dominancia de un gráfico acíclico dirigido D 1 = ( V , E 1 ), la inversión de la interpretación de un eje da como resultado una nueva relación que se podría llamar coaccesibilidad . Así, un punto ( x a , y a ) podría considerarse coaccesible desde un punto ( x b , y b ) siempre que x a ≥ x b pero y a ≤ y b . De esta manera, se puede ver que el dibujo de dominancia induce un segundo gráfico acíclico dirigido D 2= ( V , E 2 ) en el mismo conjunto de vértices. Los pares {≤ 1 , ≤ 2 } de órdenes parciales en un conjunto básico compartido que permiten dicha representación simultánea mediante un solo dibujo, interpretado en términos de accesibilidad y coaccesibilidad, se denominan codominantes. [5]
Para grafos acíclicos dirigidos cuyo orden de alcance tiene una dimensión más alta, un dibujo de dominancia débil es un dibujo en el que cada borde está orientado hacia arriba, hacia la derecha o ambos, pero en el que existen pares de vértices ( u , v ) para los cuales u domina v coordinadamente pero v no es accesible desde u en el gráfico. Decíamos que un vértice u domina a otro vértice v si las coordenadas (u_x, u_y) de u son menores o iguales a las coordenadas (v_x, v_y) de v, es decir, u_x <= v_x y u_y <= v_y considerando un plano XY. El objetivo de este estilo de dibujo es minimizar el número de rutas falsamente implícitas . [6]
