Teoría

St-grafos Planos

Un st-grafo plano es un digrafo acíclico plano con un solo vértice fuente s y un solo vértice sumidero t.

Una numeración topológica de un digrafo acíclico G es una asignación de números a los vértices de G, de forma tal que, para cada arista (u, v) de G, el número asignado a v es mayor que el asignado a u. Es decir, número(v) > número(u). Si las aristas del digrafo tienen pesos asignados, entonces tendremos que, para cada arista (u, v) de G, el número asignado a v es mayor o igual que el asignado a u más el peso de (u, v). Es decir, número(v) ≥ número(u) + peso(u, v). La numeración es óptima si el rango de números asignados a los vértices es mínimo.

Dado que el grafo es plano, podemos definir el digrafo dual G* asociado a G de la siguiente forma:

  • El conjunto de vértices de G* está formado por el conjunto de caras G. La cara externa de G se divide en dos caras denominadas cara externa izquierda s* y cara externa derecha t*.

  • Para cada arista e de G, siempre y cuando no sea la arista (s, t), G* tiene una arista e* = (f, g) donde f es la cara a la izquierda de e, denominada izquierda(e), y g es la cara a la derecha de e, denominada derecha(e).

Representación de Visibilidad

Una representación de visibilidad Γ de una st-grafo plano G traza cada vértice v como un segmento horizontal, denominado segmento vértice Γ(v), y cada arista (u, v) como un segmento vertical, denominado segmento arista Γ(u, v), tal que:

  • Los segmentos vértice no se solapan.

  • Los segmentos arista no se solapan.

  • Un segmento arista Γ(u, v) tiene su extremo más bajo en Γ(u), su extremo más alto en Γ(v) y no intersecta ningún otro segmento vértice.

Los segmentos se representan sobre un sistema de coordenadas enteras, por lo tanto, tenemos una serie de coordenadas relacionadas con cada segmento. Un segmento vértice Γ(v), por ser horizontal, está ubicado a lo largo de una coordenada del eje de ordenadas, denominada y(Γ(v)), y entre dos coordenadas del eje de abscisas, denominándose xL(Γ(v)) la coordenada izquierda y xR(Γ(v)) la coordenada derecha. Un segmento arista Γ(u, v), por ser vertical, está ubicado a lo largo de una coordenada del eje de abscisas, denominada x(Γ(u, v)), y entre dos coordenadas del eje de ordenadas, denominándose yB(Γ(u, v)) la coordenada más baja e yT(Γ(u, v)) la coordenada más alta.

Algoritmo Visibilidad

Entrada: st-grafo plano G con n vértices.
Salida: representación de visibilidad Γ de G con coordenadas enteras con área O(n2).
Complejidad: O(n)
Pasos:

  1. Construir el st-grafo plano G*.

  2. Calcular la numeración topológica óptima Y de G.

  3. Calcular la numeración topológica óptima X de G*.

  4. Para cada vértice v de G hacer:
     Trazar Γ(v) como un segmento horizontal con
     y(Γ(v)) = Y(v);
     xL(Γ(v)) = X(izquierda(v));
     xR(Γ(v)) = X(derecha(v)) - 1;

  5. Para cada arista e de G hacer:
     Trazar Γ(e) como un segmento vertical con
     x(Γ(e)) = X(izquierda(e));
     yB(Γ(e)) = Y(origen(e));
     yT(Γ(e)) = Y(destino(e));

Grafo Inicial

Representación de Visibilidad

Representación de Visibilidad con Restricciones

En esta parte veremos una variación de la representación de visibilidad donde se obliga a que algunas aristas predefinidas se mantengan verticalmente alineadas. Esta representación se denomina representación de visibilidad con restricciones y es usada como punto de partida para generar trazados poligonales y ortogonales con propiedades interesantes.

Caminos disjuntos: Permitir que G sea un st-grafo plano con n vértices. Dos caminos π1 y π2 de G son disjuntos si no tienen aristas compartidas y no se cruzan en vértices comunes, es decir, no existe un vértice v en G con aristas e1, e2, e3 y e4 colocadas en el sentido de las agujas del reloj alrededor de v, tal que e1 y e3 estén en π1, y e2 y e4 estén en π2. También, todos los pares de caminos que no tienen vértices interiores en común son disjuntos.

Algoritmo Visibilidad con restricciones

Entrada: st-grafo plano G con n vértices. Conjunto Π de caminos disjuntos que abarca todas las aristas de G.
Salida: representación de visibilidad con restricciones Γ de G con coordenadas enteras con área O(n2).
Complejidad: O(n)
Pasos:

  1. Construir el st-grafo plano GΠ con el conjunto de vértices formado por F ∪ Π y el conjunto de aristas formado por {(f, π) | f = izquierda(e) para toda arista e del camino π} ∪ {(π, g) | g = derecha(e) para toda arista e del camino π}.

  2. Calcular la numeración topológica óptima Y de G, tal que Y(s) = 0.

  3. Calcular la numeración topológica óptima X de GΠ, tal que el peso de las aristas sea igual a media unidad y X(s*) = −1/2.

  4. Para cada vértice v de G hacer:
     Trazar Γ(v) como un segmento horizontal con
     y(Γ(v)) = Y(v);
     xL(Γ(v)) = mínv∈π X(π);
     xR(Γ(v)) = máxv∈π X(π);

  5. Para cada camino π de Π hacer:
     Para cada arista e de π hacer:
      Trazar Γ(e) como un segmento vertical con
      x(Γ(e)) = X(π);
      yB(Γ(e)) = Y(origen(e));
      yT(Γ(e)) = Y(destino(e));

En el grafo inicial que utilizamos como ejemplo a continuación, están seleccionados los caminos (0, 2, 8), (0, 1, 3, 5, 6, 8) y (3, 4, 7, 8) como restricciones.

Grafo Inicial

Representación de Visibilidad con Restricciones

Trazado Poligonal Ascendente

En esta parte vamos a ver un algoritmo que construye un trazado poligonal ascendente plano de un st-grafo plano G a partir de una representación de visibilidad de G. La estrategia que sigue el algoritmo es trazar cada vértice de G en un punto arbitrario de su segmento vértice y trazar cada arista (u, v) de G como una línea poligonal de tres segmentos, cuyo segmento del medio es un subconjunto del segmento arista de (u, v).

Algoritmo Poligonal

Entrada: st-grafo plano G con n vértices.
Salida: trazado poligonal ascendente plano de G con área O(n2).
Complejidad: O(n)
Pasos:

  1. Construir una representación de visibilidad Γ de G con coordenadas enteras.

  2. Para cada vértice v de G hacer:
     Reemplazar el segmento vértice Γ(v) por un punto arbitrario
     P(v) = (x(v), y(v)) en Γ(v);

  3. Para cada arista e = (u, v) de G hacer:
     Si e es una arista corta, es decir, y(v) − y(u) = 1
      Reemplazar el segmento arista Γ(u, v) por un segmento desde P(u) hasta P(v).
     De lo contrario, es una arista larga
      Reemplazar el segmento arista Γ(u, v) por una línea poligonal desde P(u) hasta
      P(v) pasando por los puntos (x(Γ(u, v)), y(u) + 1) y (x(Γ(u, v)), y(v) – 1).

La selección del lugar donde se ubica el punto que reemplaza un segmento vértice influye en el número de codos de las aristas del trazado. El punto P(v) se ubica en la intersección del segmento vértice Γ(v) con una arista larga incidente en v, siempre que esta exista.

Grafo Inicial

Trazado Poligonal Ascendente

Trazado Poligonal Ascendente con Restricciones

El algoritmo de trazado poligonal que hemos visto en el apartado anterior puede ser extendido para utilizar la representación de visibilidad con restricciones. En este caso, cada camino no debe tener vértices internos en común con el resto, lo que los convierte en caminos disjuntos por definición.

El algoritmo descrito en esta sección consigue que todos los vértices internos de un camino estén alineados verticalmente. Esto hace que el trazado poligonal con restricciones sea interesante para la visualización de caminos específicos. Por ejemplo, podemos aplicar el trazado a un diagrama de PERT para que queden alineadas las tareas del camino crítico.

Algoritmo Poligonal con restricciones

Entrada: st-grafo plano G con n vértices. Conjunto Π de caminos sin vértices internos en común de G.
Salida: trazado poligonal ascendente plano de G, tal que, para cada camino π de Π, todos los vértices internos de π están verticalmente alineados. Área igual a O(n2).
Complejidad: O(n)
Pasos:

  1. Construir una representación de visibilidad con restricciones Γ de G con respecto a Π.

  2. Para cada vértice v de G hacer:
     Reemplazar el segmento vértice Γ(v) por un punto
     P(v) = (x(v), y(v)) en Γ(v) de la siguiente forma:
      Si v pertenece a un camino π de Π
       x(v) = X(π);
       y(v) = Y(π);

  3. Para cada arista e = (u, v) de G hacer:
     Si e es una arista corta, es decir, y(v) − y(u) = 1
      Reemplazar el segmento arista Γ(u, v) por un segmento desde P(u) hasta P(v).
     De lo contrario, es una arista larga
      Reemplazar el segmento arista Γ(u, v) por una línea poligonal desde P(u) hasta
      P(v) pasando por los puntos (x(Γ(u, v)), y(u) + 1) y (x(Γ(u, v)), y(v) – 1).

En el grafo inicial que utilizamos como ejemplo a continuación, están seleccionados los caminos (0, 2, 8), (0, 1, 3, 5, 6, 8) y (3, 4, 7, 8) como restricciones.

Grafo Inicial

Trazado Poligonal Ascendente con Restricciones

Trazado Ortogonal Plano

En esta parte describiremos un algoritmo para crear el trazado ortogonal plano de un grafo plano biconexo G  a partir de la representación de visibilidad con restricciones. El conjunto de caminos disjuntos es determinado por el propio algoritmo. La condición de que el grafo sea biconexo está impuesta por el algoritmo de orientación bipolar que se aplica como paso inicial del algoritmo para convertir un grafo no dirigido G en un st-grafo.

Otra restricción que debe cumplir el grafo inicial es que solo puede tener vértices de grado menor o igual a cuatro. Esto viene dado por las características del trazado ortogonal que solo permite representar las aristas utilizando segmentos horizontales y verticales.

Algoritmo Ortogonal

Entrada: grafo biconexo plano G con n vértices de grado menor o igual a cuatro.
Salida: trazado ortogonal plano de G con área igual a O(n2).
Complejidad: O(n)
Pasos:

  1. Construir un st-grafo D a partir de una orientación bipolar de G.

  2. Crear un conjunto de n – 2 caminos dirigidos de D asociados con los vértices distintos de s y t. El proceso es el siguiente:
    Para cada vértice v de D distinto de s y t hacer:
     Crear un camino πv con dos aristas e’ y e’’.
      Si v tiene solo dos aristas entrantes,
       e’ es la arista entrante situada más a la izquierda de v.
       e’’ es la arista saliente situada más a la derecha de v.
      Si v tiene una o tres aristas entrantes,
       e’ es la arista entrante situada en el medio de las otras aristas entrantes de v.
       e’’es la arista saliente situada en el medio de las otras aristas salientes de v.
     Unificar los caminos que compartan aristas, lo cual produce un conjunto Π de
     caminos disjuntos.

  3. Construir una representación de visibilidad con restricciones Γ de D con respecto a Π.

  4. Para cada vértice v de D hacer:
     Si v es distinto de s y t,
      Trazar v en la intersección P(v) del segmento vértice Γ(v) con los segmentos
      arista del camino πv.
     Si v es el vértice s,
      Trazar v en la intersección P(v) del segmento vértice Γ(v) con el segmento arista
      de la arista saliente situada en el medio de las demás.
     Si v es el vértice t,
      Trazar v en la intersección P(v) del segmento vértice Γ(v) con el segmento arista
      de la arista entrante situada en el medio de las demás.

  5. Para cada arista e = (u, v) de D hacer:
     Si u y v son distintos de s y t,
      Trazar e como una línea poligonal que pasa por los puntos:
      P(u), la intersección del segmento vértice Γ(u) con el segmento arista Γ(e),
      la intersección del segmento arista Γ(e) con el segmento vértice Γ(v), y P(v).
      La línea poligonal está formada por tres segmentos donde el primero y el
      último pueden estar vacíos.
     Si u o v es s,
      Trazar e como una línea poligonal que pasa por los puntos:
      P(u), la intersección del segmento vértice Γ(u) con el segmento arista Γ(e),
      la intersección del segmento arista Γ(e) con el segmento vértice Γ(v), y P(v).
      Si el vértice s tiene grado cuatro, se deben resolver los cortes entre las
      aristas.
     Si u o v es t,
      Trazar e como una línea poligonal que pasa por los puntos:
      P(u), la intersección del segmento vértice Γ(u) con el segmento arista Γ(e),
      la intersección del segmento arista Γ(e) con el segmento vértice Γ(v), y P(v).
      Si el vértice t tiene grado cuatro, se deben resolver los cortes entre las
      aristas.

Grafo Inicial

Trazado Ortogonal Plano

Trazado de Dominancia Rectilíneo

Un trazado de dominancia de un digrafo G es un trazado Γ de G, tal que, para cada par de vértices u y v, hay un camino dirigido desde u hasta v en G, si y solo si x(u) ≤ x(v) e y(u) ≤ y(v) en Γ. Observar que estas dos condiciones no se pueden cumplir al mismo tiempo en el caso de la igualdad dado que dos vértices distintos deben estar situados en puntos diferentes.

En esta parte vamos a ver un algoritmo para generar el trazado de dominancia rectilíneo a partir de un digrafo reducido. Permitir que G sea un digrafo acíclico. Una arista (u, v) de G es transitiva si hay otro camino dirigido en G que permita ir desde u hasta v. Un digrafo acíclico es reducido si no tiene aristas transitivas.

Algoritmo Dominancia rectilíneo

Entrada: st-grafo plano reducido G con n vértices.
Salida: trazado de dominancia rectilíneo Γ de G con área igual a O(n2).
Complejidad: O(n)
Pasos:

  1. Preprocesamiento: Construir una estructura de datos para G, donde cada vértice v tiene asociado una lista de sus aristas salientes ordenadas según el sentido de las agujas del reloj. Esta lista es doblemente enlazada por medio de los punteros siguiente(e) y anterior(e), y es accedida a través de los punteros primeraSaliente(v) y últimaSaliente(v) hacia sus aristas salientes más a la izquierda y más a la derecha, respectivamente. Además, v tiene los punteros primeraEntrante(v) y últimaEntrante(v) hacia sus aristas entrantes más a la izquierda y más a la derecha, respectivamente. Por último, cada arista e = (u, v) mantiene un puntero cabecera(e) hacia v.

  2. Trazado Preliminar: Asignar las coordenadas preliminares X e Y.
     Asignar la coordenada preliminar X.
     Hacer contador := 0 e invocar etiquetaX(s).

     procedure etiquetaX(vértice v)
     begin
      X(v) := contador;
      contador := contador + 1;
      if v ≠ t then
       e = primeraSaliente(v);
       repeat
        w = cabecera(e);
        if e = últimaEntrante(w) then
         etiquetaX(w);
        end if;
        e = siguiente(e);
       until (e = nil);
      end if;
     end etiquetaX;

     Asignar la coordenada preliminar Y.
     Hacer contador := 0 e invocar etiquetaY(s).

     procedure etiquetaY(vértice v)
     begin
      Y(v) := contador;
      contador := contador + 1;
      if v ≠ t then
       e =últimaSaliente(v);
       repeat
        w = cabecera(e);
        if e =primeraEntrante(w) then
         etiquetaY(w);
        end if;
        e =anterior(e);
       until (e = nil);
      end if;
     end etiquetaY;

  3. Compactación: Asignar las coordenadas finales x e y.
     Construir dos listas de vértices ordenados de menor a mayor según las coordenadas X
     e Y a través de los punteros siguienteX(v) y siguienteY(v).
     Asignar la coordenada final x.
      Permitir que u sea el vértice para el cual X(u) = 0.
      x(u) = 0;
      while siguienteX(u) ≠ nil do
       v = siguienteX(u);
       if Y(u) > Y(v) or (primeraSaliente(u) = últimaSaliente(u) and
       primeraEntrante(v) = últimaEntrante(v)) then
        x(v) = x(u) + 1;
       else
        x(v) = x(u);
       end if;
       u = v;
      end do;
     Asignar la coordenada final y.
      Permitir que u sea el vértice para el cual Y(u) = 0.
      y(u) = 0;
      while siguienteY(u) ≠ nil do
       v = siguienteY(u);
       if X(u) > X(v) or (primeraSaliente(u) = últimaSaliente(u) and
       primeraEntrante(v) = últimaEntrante(v)) then
        y(v) = y(u) + 1;
       else
        y(v) = y(u);
       end if;
       u = v;
      end do;

Grafo Inicial

Trazado de Dominancia Rectilíneo

Trazado Dominancia Poligonal

El algoritmo que construye el trazado de dominancia rectilíneo puede ser modificado para funcionar con st-grafos planos mediante la inserción de vértices ficticios en cada arista transitiva. El resultado es un algoritmo que construye un trazado poligonal con un número máximo de codos menor al establecido por el algoritmo que genera el trazado poligonal a partir de la representación de visibilidad.

Algoritmo Dominancia poligonal

Entrada: st-grafo plano G con n vértices.
Salida: trazado de dominancia poligonal Γ de G con área igual a O(n2).
Complejidad: O(n)
Pasos:

  1. Si G no es reducido, sustituir cada arista transitiva (u, v) por un nuevo vértice x y dos aristas (u, x) y (x, v). Denominar G’ al st-grafo plano reducido resultante.

  2. Construir un trazado de dominancia rectilíneo Γ’ de G’ utilizando el Algoritmo Dominancia rectilíneo.

  3. Reemplazar cada vértice ficticio introducido en el paso 1 por un codo en la arista original.

Grafo Inicial

Trazado Poligonal Ascendente

Contenidos