Gráfico st-planar

Un gráfico plano st es una orientación bipolar de un gráfico plano para el cual tanto la fuente como el sumidero de la orientación están en la cara exterior del gráfico. Es decir, es un grafo dirigido dibujado sin intersecciones en el plano de tal manera que no hay ciclos dirigidos en el grafo, exactamente un vértice del grafo no tiene arcos de entrada, exactamente un vértice del grafo no tiene arcos de salida, y estos dos vértices especiales se encuentran en la columna de la cara exterior [1] .

En el dibujo, cada cara del gráfico debe tener la misma estructura: hay un vértice que sirve como origen de la cara, un vértice sirve como sumidero de la cara y todos los bordes dentro de la cara están dirigidos a lo largo de dos caminos desde la fuente al fregadero. Si dibujamos un borde adicional desde el sumidero del gráfico st -planar de regreso a la fuente a lo largo de la cara exterior y luego construimos el gráfico dual (orientando cada borde dual en el sentido de las agujas del reloj en relación con el borde original), entonces nuevamente obtenemos un st -planar gráfico extendido por un borde adicional de la misma manera [1 ] .

Teoría del orden

Estos gráficos están estrechamente relacionados con los conjuntos y retículos parcialmente ordenados . El diagrama de Hasse de un poset es un grafo acíclico dirigido cuyos vértices son el conjunto de elementos en los que existe una arista de x a y para cada par x , y de elementos para los que existe un orden parcial pero para los que no existe z do . Un poset forma una red completa si y solo si cualquier subconjunto de elementos tiene un solo límite inferior mayor y un solo límite superior más pequeño, y la dimensión ordinal poset es el número más pequeño de conjuntos lineales ordenados en el mismo conjunto de elementos cuya intersección es el orden parcial dado. Si los vértices de un gráfico st -planar están parcialmente ordenados de forma alcanzable, entonces este orden siempre forma una red bidimensional completa cuyo diagrama de Hasse es una contracción transitiva del gráfico dado. Por el contrario, el diagrama de Hasse de cualquier red bidimensional completa es siempre un gráfico de st -planar [2] .

Dibujo de gráficos

Con base en esta propiedad bidimensional de orden parcial, cualquier gráfico st -planar se puede representar como un patrón dominante en el que para cada dos vértices u y v hay un camino de u a v si y solo si ambas coordenadas u son menor que, que las coordenadas correspondientes v [3] . Las coordenadas de dicho dibujo se pueden usar como una estructura de datos que se puede usar para verificar que desde un vértice de un gráfico st -planar es posible llegar a otro vértice en tiempo constante por solicitud. Rotar la figura 45° da una representación plana ascendente del gráfico. Un grafo acíclico dirigido G tiene una representación plana ascendente si y solo si G es un subgrafo de un grafo st -planar [4] .

Notas

1. ↑ 1 2 Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. 4.2 Propiedades de los Digrafos Acíclicos Planares // Dibujo de Grafos: Algoritmos para la Visualización de Grafos. - Prentice Hall , 1998. - S. 89-96. — ISBN 978-0-13-301615-4 . .
2. ↑ Platt CR Redes planas y gráficos planos // Journal of Combinatorial Theory . - 1976. - T. 21 , núm. 1 . — S. 30–39 . - doi : 10.1016/0095-8956(76)90024-1 . .
3. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 112–127 §4.7 Dibujos de Dominancia.
4. ↑ Giuseppe Di Battista, Roberto Tamassia. Algoritmos para representaciones planas de dígrafos acíclicos // Informática Teórica . - 1988. - T. 61 , núm. 2-3 . - doi : 10.1016/0304-3975(88)90123-5 . .