Esta sección trata de explicar en que consiste el algoritmo de inmersión implementados por la aplicación, de modo que puedan comprenderse mejor los pasos que efectúa el programa.

 

 ALGORITMO DE CHROBAK Y PAYNE

 Se presenta un algoritmo en tiempo lineal que dado un grafo plano G, de n vértices, encuentra una inmersión de G en una cuadrícula (2n-4) x (n-2) tal que las aristas de G sean segmentos rectilíneos.

Este algoritmo fue desarrollado en 1989 [CP89] pero no publicado. Se han realizado progresos en éste tema desde entonces. En particular, Schnyder [Sch90] mostró una técnica diferente que proporcionaba un algoritmo de inmersión en tiempo lineal, en una cuadrícula pequeña de  (n-2)x(n-2). Resulto, sin embargo, que su resultado no eliminaba el interés de nuestro algoritmo, posiblemente porque nuestra aproximación es mas fácil de implementar, y el resultado de la inmersión suele ser mas estética.

Consta de tres pasos fundamentales:

1.               Triangulación maximal

2.               Ordenación canónica de los vértices.

3.               Colocación de los vértices.

 

            En 1) se incluyen las aristas necesarias para la obtención del grafo triangulado.

En 2) se determina el orden en el que los vértices van a ser procesados.

En 3) se construye el dibujo iterativamente, según la ordenación anterior, y en cada paso se sitúa un vértice en una determinada posición de la cuadrícula.

 

TRIANGULACION


            Para realizar la triangulación de las regiones de un grafo existen numerosos algoritmos, pero su estudio no es el objetivo de este proyecto, por lo que aquí se utilizará un método más intuitivo para realizar dicha triangulación, que aunque no es el más eficiente, si es eficaz; y de esta manera conseguir un grafo con las características deseadas para la aplicación del algoritmo de inmersión plana, que ese si es el objetivo de este proyecto.

 

Una sencilla manera de hacerlo seria reconocer los vértices que delimitan una región, y encontrar un vértice de entre estos, de manera que todas las aristas que hubiese que añadir tuviesen el origen o el destino en dicho vértice; de ésta manera se evitaría la introducción de cortes de aristas de manera que el grafo dejara de ser plano, y por lo tanto perdiese ésta cualidad.

El numero de aristas a introducir en una región delimitada por V vértices, es:V-3

 

               

                                                 Figura 5.

              

La figura 5. representa una región de seis aristas. Para triangular dicha región se necesitaría incluir: v-3= 6-3 = 3 aristas. Sin embargo, no son válidas 3 aristas al azar, sino que su inclusión no debe hacer perder la planaridad del grafo al que pertenece dicha region; por lo tanto la manera más segura de introducir aristas sin cortes entre si, es que todas las aristas introducidas tengan un vértice en común.

De ésta manera la región anterior triangulada quedaría como se muestra en la figura 6. Como puede verse, el vértice en común a todas las aristas introducidas (en azul) es el 1.

 

                  

                                                 Figura 6.

 

ORDENACION CANÓNICA DE LOS VÉRTICES

 

Antes de explicar el método utilizado en dicha ordenación, se tendrá en cuenta el siguiente lema:

 

Lema 0: Sea G un grafo simple y plano y C un ciclo de G. Entonces existe un vértice en C que no es incidente a ninguna cuerda interior.

 

Demostración: Sea C = {u1, u2,…..uk}

Si C no tiene cuerdas interiores, la demostración es obvia.

Si C tiene cuerdas interiores, consideramos la cuerda interior ui,uj  (j > i+1), con j-i minimal.

 

Entonces, ui+1 no es incidente con ninguna cuerda. ÿ

Para realizar la ordenación canónica de los vértices se utiliza el siguiente lema probado por Fraysseix, Pach y Pollack en [FPP88, FPP90].

 

Lema 1: Sea G un grafo plano maximal de n vértices, con n 3, (del que se conoce una inmersión), y sean u,v,w, los vértices en la frontera de su cara exterior. La ordenación canónica es un etiquetado de los vértices de G como una sucesión v1,..vn tal que v1 = u, v2 = v y vn= w,  y para cada k, con  n   k 3 se cumple:

                          

  

a)     El subgrafo Gk-1 de G inducido por  v1,..vk-1   es biconexo y la frontera de su cara exterior es un ciclo Ck-1  conteniendo a la arista uv.

b)     El vértice vk está  en la cara exterior de Gk-1   son consecutivos en el camino Ck-1  - uv.

                                              

 

                                                                                   

Prueba: Se presentará sólo un esquema.

Sea Cn = (v1, v2,... vn ) la cara externa de G.

Inductivamente se supone que  vn , vn-1, .. vk+1, están definidos, y que los grafos Gn, Gn-1,.. Gk+1, satisfacen el lema 1. Entonces existe un vértice v en Gk+1, tal que v Ï { v1, v2 }  que tiene exactamente dos vecinos en el ciclo, Ck+1. Por lo que no es incidente de ninguna cuerda de Ck+1.

Se considera vk= v.  ÿ

 

Se definirá el etiquetado de los vértices: vn, vn-1,…. v3  por inducción. 

Primeramente se elegirán  los vértices de una región triangular cualquiera. Estos se etiquetaran como v1, v2, y vn. 

Cn = {v1, v2, y vn }      Gn = G     u= v1    v= v2   

 

Se define el grafo Gn-1, como el grafo anterior, sin el vértice etiquetado como vn:

Gn-1= G- {vn} 

 

Por G maximal, los vecinos de w forman un ciclo Cn-1 que contiene la arista uv y éste ciclo es el borde de la cara exterior de Gn-1.

 

 

 

A continuación, suponemos que vn, vn-1, ….vk+1, definidos Gn, Gn-1, …Gk+1 satisfacen las condiciones a) y b) del lema 1. 

Los vértices se etiquetaran iterativamente, de manera que para un ciclo k:

 

Gk = Gk+1 – {vk+1}           y             Ck es el ciclo exterior de Gk

 

Por el lema 0, existe un z Î Ck no incidente con cuerda interior. Se toma vk= z, así  Gk y vk cumplen las condiciones a), y b) del lema 1.

 

 

La existencia de tal ordenación canónica se prueba en [FPP90], donde también se proporciona un algoritmo lineal para construirla. Aunque una descripción más sencilla de ese algoritmo se encuentra en [HS98].

 

Un prerrequisito para poder aplicar el algoritmo es tener una inmersión (plana) del grafo, es decir, una estructura de datos que describa la ordenación circular de los vecinos de cada vértice del grafo en algún dibujo plano. Un algoritmo también lineal para construir esa inmersión plana se describe en [CNAO85] y también en [MM96], o bien, se pueden utilizar los algoritmos que comprueban la planaridad de un grafo general y que pueden tener como salida esa inmersión plana.

 

COLOCACIÓN DE LOS VÉRTICES

 

En éste tercer paso del algoritmo de [CP90] es donde se colocan los vértices del grafo en puntos de la cuadrícula, con coordenadas enteras, para conseguir una inmersión plana rectilínea del grafo. Este proceso es iterativo, colocándose un vértice en cada paso según el orden  que determina la ordenación canónica de los vértices.

 

La idea básica del algoritmo, es colocar cada vértice por encima de los vértices adyacentes ya colocados en la figura, de manera que se visualicen desde su posición todos ellos y se pueda, por tanto, trazar las aristas sin producir cruces de aristas. Concretamente el vértice se situará en el punto, de la cuadrícula, intersección de la recta con pendiente +1 que pasa por el vértice más a la izquierda y la recta con pendiente -1 que pasa por el vecino más a la derecha.

 

A veces será necesario correr hacia la derecha junto con los vértices adyacentes ya colocados, ciertos vértices relacionados con ellos, situados por debajo y adyacentes, para no introducir de manera inadvertida cortes de aristas y perder, por tanto, la planaridad. Esta situación se puede observar con el siguiente ejemplo:

 

 

A cada vértice vk, se asocia un conjunto de vértices L(vk) que se moverán  junto con vk cada vez que se ajuste su posición.

 

NOTACIÓN

Dados dos puntos Q = (x1,y1) y R = (x2,y2), con coordenadas enteras, se denota con µ(Q,R) la intersección de la recta que pasa por Q con pendiente +1 con la recta que pasa por R con pendiente -1. Es decir:

      µ(Q,R) =  µ( (x1,y1), (x2,y2) ) = ½ (x1 - y1 + x2  + y2 , -x1 + y1 + x2  + y2  )

Con  P(v) = (x(v),y(v)) se denota la posición del vértice v en la cuadrícula.

A cada vértice v se le asocia un conjunto, que notaremos L(v), formado por los vértices que hay que mover cada vez que cambie la posición de v.

Se define la distancia entre puntos:

           d1 (Q,R)= d1 ((x1,y1), (x2,y2)) = │x2 - x1 │+│ y2- y1

 

Si d1 (Q,R)  es par entonces también lo son los valores ((x1 - y1 + x2  + y2  ) y  (-x1 + y1 + x2  + y2 ); por tanto, si Q y R tienen coordenadas enteras entonces el punto  µ(Q,R)  es un punto de la cuadrícula con coordenadas enteras también.

 

INICIALIZACION

El algoritmo empieza situando a v1 = u, v2 = v y v3 en un triangulo:

 

-                  P(v1) = (0,0)   P(v2) = (2,0)    P(v3)= (1,1)

-                  L(vi) = {vi}  para i= 1,2,3.

 

ITERACION

En cada paso se añade un vértice vk a los ya colocados v1,…vk-1 formando el grafo Gk. El invariante del bucle  es que el contorno de Gk, el ciclo Ck, es una figura parecida a un triángulo, donde la parte superior se asemeja un poco a una cadena montañosa. Concretamente en cada paso k-ésimo del algoritmo se verifican:

 

-                  P(v1) = (0,0),  P(v2) = (2k-4,0).

-                  Ck =  < w1,w2,.. wn>, para algún m, donde w1= v1, wn= v2

   Y además, x(w1)   x(wm).

-                  La pendiente de cada segmento (P(wi), P(wi+1)), para i = 1,..,m-1 es +1 o -1.

 

 

De ahora en adelante la secuencia w1, ... wm, se conocerá  como el contorno de Gk-1. Siendo wp,...wq los vecinos de vk, en Ck-1. Se considerará que vk, cubre a los vértices wp+1...wq-1.

 

 

Por la ordenación canónica podemos suponer que todos los vértices vecinos de vk en el ciclo Ck-1 son consecutivos, si los llamamos wp,wp+1,..,wq, entonces podemos añadir vk a Gk-1 mediante los siguientes pasos:

 

1.               para cada v       hacer x(v):= x(v)+2;

   (estos puntos se mueven 2 unidades a la derecha)

 

2.               para cada v       hacer x(v):= x(v)+1;

  (estos puntos se mueven 1 unidades a la derecha)

 

1.               P(vk)= m (P(wp), P(wq));

 

2.                L(vk) = {vk} È   ;

 

 

Por los pasos 1 y 2 se mueven los puntos P(wi) hacia la derecha en la cuadrícula de forma que todos los vecinos de vk son visibles desde P(vk). Además, con cada vértice v se mueve también todo el conjunto de vértices L(v), que son los que están por debajo y relacionados con él, para evitar introducir cortes inadvertidamente. De ésta forma, se asegura que todos los vecinos de vk serán  visibles desde P(vk)

 

 

Por la propiedad (h3) se cumple que d1(P(wp), P(wq)) es par, y, por tanto m (P(wp), P(wq)) es siempre un punto de la cuadrícula con coordenadas enteras.

 

 

Al final del proceso se obtiene una inmersión rectilínea del grafo, donde las condiciones (h1) (h2)(h3) se satisfacen,  que tiene forma de triangulo, con vértices:

 

     P(v1)= (0,0)          P(v2)= (2n-4,0)            P(vn)= (n-2, n-2)

 

Comentarios finales

Como ya se  mencionó anteriormente, se han realizado progresos recientemente. Schnyder [Sch90] ha desarrollado otra técnica para obtener una inmersión en tiempo lineal en una cuadrícula (n-2)x (n-2). También se pone de manifiesto que el método de Chrobak y Payne puede mejorarse utilizando una cuadrícula de ese tamaño: cuando se coloca vk, se mueven todos los vértices wp+1,... wn un lugar hacia la derecha, y luego se coloca vk en P(vk) = (x,y) donde x= x(wp) +1 y  y= y(wq)+x(wq) – x , esta es la arista (vk, wq) con pendiente –1.

Todas las pendientes deben pertenecer al conjunto [0, )  {-1}. Las pruebas de su corrección son similares. La cuadrícula utilizada es menor, y la inmersión ocupa el triangulo de vértices :

       P(v1) = (0,0)             P(v2) = ( n-2, 0)       P(vn) = (1, n-2)

El dibujo obtenido es asimétrico, y no muy estético.

 

La elección de un algoritmo u otro, dependerá de la aplicación para la que se necesite.

 

El problema de los dibujos convexos de grafos planos ha atraído la atención recientemente. Vease [CyN84, CON85, Ka92]. Esto es debido a que el método en FPP88, FPP90, al igual que el algoritmo de Schnyder [Sch90], triangula un grafo dado antes de la inmersión, eliminando las aristas introducidas después, esto puede producir dibujos no muy estéticos cuando el grafo inicial está algo disperso.

Goos Kant [Ka92], obtuvo un algoritmo linear basado en el método aquí expuesto que obtenía dibujos convexos de grafos planos en una cuadrícula de (2n-4)x(n-2). Recientemente Chrobak y Kant [Ck93], han observado que usando las mejoras de Schnyders en el algoritmo de Chobak y Payne, éste puede ser modificado de manera que se obtengan inmersiones convexas en una cuadrícula (n-2)x(n-2). Un resultado similar han obtenido independientemente  Schyder y Trotter [ST92] usando la técnica de [Sch90].