grafo st -planar

En teoría de grafos , un grafo st -planar es una orientación bipolar de un grafo plano en la que tanto el origen como el destino de la orientación se encuentran en la cara exterior del grafo. Es decir, es un grafo dirigido dibujado sin cruces en el plano, de tal manera que no hay ciclos dirigidos en el grafo, exactamente un vértice del grafo no tiene aristas entrantes, exactamente un vértice del grafo no tiene aristas salientes, y estos dos vértices especiales se encuentran en la cara exterior del grafo. ^{[ 1 ]}

Dentro del dibujo, cada cara del grafo debe tener la misma estructura: hay un vértice que actúa como origen de la cara, un vértice que actúa como destino de la cara, y todas las aristas dentro de la cara están dirigidas a lo largo de dos caminos desde el origen hasta el destino. Si se dibuja una arista adicional desde el destino de un grafo st -planar de vuelta al origen, a través de la cara exterior, y luego se construye el grafo dual (orientando cada arista dual en sentido horario con respecto a su arista primal), entonces el resultado es nuevamente un grafo st -planar, aumentado con una arista adicional de la misma manera. ^{[ 1 ]}

Estos grafos están estrechamente relacionados con conjuntos parcialmente ordenados y retículos . El diagrama de Hasse de un conjunto parcialmente ordenado es un grafo dirigido acíclico cuyos vértices son los elementos del conjunto, con una arista de x a y para cada par x , y de elementos para los cuales x  ≤ y en el orden parcial pero para los cuales no existe z con x ≤ y ≤ z . Un conjunto parcialmente ordenado forma un retículo completo si y solo si cada subconjunto de elementos tiene una única cota inferior máxima y una única cota superior mínima, y ​​la 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 alcanzabilidad, entonces este ordenamiento siempre forma un retículo completo bidimensional, cuyo diagrama de Hasse es la reducción transitiva del grafo dado. Recíprocamente, el diagrama de Hasse de todo retículo completo bidimensional es siempre un grafo st -planar. ^{[ 2 ]}     

Basándose en esta propiedad de orden parcial bidimensional, a cada grafo st -planar se le puede asignar un dibujo de dominancia , en el que para cada par de vértices u y v existe un camino de u a v si y solo si ambas coordenadas de u son menores que las coordenadas correspondientes de v . ^{[ 3 ]} Las coordenadas de dicho dibujo también pueden usarse como una estructura de datos que permite comprobar si un vértice de un grafo st -planar puede alcanzar a otro en tiempo constante por consulta. Al rotar dicho dibujo 45° se obtiene un dibujo planar ascendente del grafo. Un grafo dirigido acíclico G tiene un dibujo planar ascendente si y solo si G es un subgrafo de un grafo st -planar. ^{[ 4 ]}