El dibujo de dominancia es un estilo de dibujo de grafos acíclicos dirigidos que hace que las relaciones de alcanzabilidad entre vértices sean visualmente evidentes. En el dibujo de dominancia, los vértices se colocan en puntos distintos del plano euclidiano y un vértice v es alcanzable 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 planar acíclico dirigido con una única fuente y un único sumidero, ambos en la cara exterior de alguna incrustación del grafo, tiene un dibujo de dominancia. El algoritmo de izquierda-derecha para encontrar estos dibujos establece la coordenada x de cada vértice como su posición en un orden de búsqueda en profundidad del grafo, comenzando con s y priorizando las aristas en orden de derecha a izquierda, y estableciendo la coordenada y para que se obtenga de la misma manera pero priorizando las aristas en orden de izquierda a derecha. Los algoritmos de dibujo de dominancia típicos 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 preservan 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 aristas en línea recta. [1] [2]
Para los gráficos st -planares que no se reducen transitivamente, se puede obtener un gráfico transitivamente reducido equivalente subdividiendo cada borde. Sin embargo, un dibujo en línea recta del gráfico transitivamente reducido 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 planar no es necesariamente un dibujo planar hacia arriba , porque algunos bordes pueden ser horizontales, pero rotarlo 45° necesariamente da un dibujo planar hacia arriba. [1] En una comparación con otros métodos para dibujar gráficos acíclicos dirigidos, se encontró que el algoritmo izquierda-derecha (junto con un paso de preprocesamiento de planarización) funcionaba bien en términos del área de los dibujos que produce, la cantidad de curvas y la relación de aspecto del dibujo, pero menos bien en la longitud total del borde. [3]
Un grafo acíclico dirigido (independientemente de su planaridad) tiene un dibujo de dominancia si y solo si el conjunto parcialmente ordenado de sus vértices, ordenado por alcanzabilidad, tiene dimensión de orden dos. El dibujo de dominancia (rotado) de un grafo acíclico dirigido transitivamente reducido puede usarse como un diagrama de Hasse del orden parcial correspondiente. [4]
Dado un dibujo de dominancia de un grafo acíclico dirigido D 1 = ( V , E 1 ), invertir la interpretación de un eje da como resultado una nueva relación que se podría llamar co-alcanzabilidad . Por lo tanto, un punto ( x a , y a ) podría considerarse co-alcanzable 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 grafo 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 tal representación simultánea por un único dibujo, interpretado en términos de alcanzabilidad y co-alcanzabilidad, se denominan codominantes. [5]
Para grafos acíclicos dirigidos cuyo orden de alcanzabilidad tiene mayor dimensión, un dibujo de dominancia débil es un dibujo en el que cada arista está orientada hacia arriba, hacia la derecha o ambas, pero en el que existen pares de vértices ( u , v ) para los cuales u domina a v en términos de coordenadas pero v no es alcanzable desde u en el grafo. Decimos 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 en este estilo de dibujo es minimizar el número de tales caminos falsamente implícitos . [6]