En la teoría de grafos , un grafo st -planar es una orientación bipolar de un grafo 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 gráfico dirigido dibujado sin cruces en el plano, de tal manera que no hay ciclos dirigidos en el gráfico, exactamente un vértice del gráfico no tiene aristas entrantes, exactamente un vértice del gráfico no tiene aristas salientes, y estos dos los vértices especiales se encuentran en la cara exterior del gráfico. [1]
Dentro del dibujo, cada cara del gráfico debe tener la misma estructura: hay un vértice que actúa como fuente de la cara, un vértice que actúa como sumidero de la cara y todos los bordes dentro de la cara se dirigen a lo largo de dos trayectorias. desde la fuente hasta el fregadero. Si uno dibuja un borde adicional desde el sumidero de un gráfico st -planar de regreso a la fuente, a través de la cara exterior, y luego construye el gráfico dual (orientado cada borde dual en el sentido de las agujas del reloj con respecto a su borde primario), entonces el resultado es nuevamente un st -planar graph, aumentado con un borde adicional de la misma manera. [1]
Estos gráficos están estrechamente relacionados con retículas y conjuntos parcialmente ordenados . El diagrama de Hasse de un conjunto parcialmente ordenado es un gráfico acíclico dirigido cuyos vértices son los elementos de ajuste, con un borde de x a y para cada par x , y de elementos para los cuales x ≤ y en el orden parcial, pero para las que no hace existe z con x ≤ y ≤ z . Un conjunto parcialmente ordenado forma un entramado completo si y solo si cada subconjunto de elementos tiene un límite inferior máximo único y un límite superior mínimo único, y elLa dimensión de orden de un conjunto parcialmente ordenado es el menor número de órdenes totales en el mismo conjunto de elementos cuya intersección es el orden parcial dado. Si los vértices de un grafo st -planar están parcialmente ordenados por accesibilidad, entonces este orden siempre forma un retículo completo bidimensional, cuyo diagrama de Hasse es la reducción transitiva del grafo dado. Por el contrario, el diagrama de Hasse de cada retícula completa bidimensional es siempre un gráfico st -planar. [2]
Sobre la base de esta propiedad orden parcial de dos dimensiones, cada st gráfico -planar se puede dar un dibujo dominio , en el que por cada dos vértices u y v existe un camino de u a v si y sólo si ambas coordenadas de u son más pequeños que las coordenadas correspondientes de v . [3] Las coordenadas de dicho dibujo también se pueden usar como una estructura de datos que se puede usar para probar si un vértice de un gráfico st -planar puede alcanzar otro en tiempo constante por consulta. Al girar un dibujo de este tipo en 45 ° se obtiene un dibujo plano hacia arribadel gráfico. Un gráfico acíclico dirigido G tiene un dibujo plano hacia arriba si y solo si G es un subgrafo de un gráfico st -planar. [4]