stringtranslate.com

Dibujo plano ascendente

Un dibujo plano ascendente
Este DAG planar no tiene dibujo ascendente, porque su fuente y su sumidero no pueden estar ambos en la misma cara.

En el dibujo de grafos , un dibujo plano ascendente de un grafo acíclico dirigido es una incrustación del grafo en el plano euclidiano , en el que las aristas se representan como curvas ascendentes monótonas que no se cruzan . Es decir, la curva que representa cada arista debe tener la propiedad de que cada línea horizontal la interseca en como máximo un punto, y no pueden intersectarse dos aristas excepto en un punto final compartido. [1] En este sentido, es el caso ideal para el dibujo de grafos en capas , un estilo de dibujo de grafos en el que las aristas son curvas monótonas que pueden cruzarse, pero en el que los cruces deben minimizarse.

Caracterizaciones

Un grafo acíclico dirigido debe ser plano para tener un dibujo plano ascendente, pero no todos los grafos acíclicos planos tienen dicho dibujo. Entre los grafos acíclicos dirigidos planos con una única fuente (vértice sin aristas entrantes) y sumidero (vértice sin aristas salientes), los grafos con dibujos planos ascendentes son los grafos st -planares , grafos planos en los que la fuente y el sumidero pertenecen a la misma cara de al menos una de las incrustaciones planares del grafo. De manera más general, un grafo G tiene un dibujo plano ascendente si y solo si es dirigido y acíclico, y es un subgrafo de un grafo st -planar en el mismo conjunto de vértices. [2]

En una incrustación ascendente, los conjuntos de aristas entrantes y salientes incidentes a cada vértice son contiguos en el orden cíclico de las aristas en el vértice. Se dice que una incrustación plana de un grafo acíclico dirigido dado es bimodal cuando tiene esta propiedad. Además, el ángulo entre dos aristas consecutivas con la misma orientación en un vértice dado puede etiquetarse como pequeño si es menor que π, o grande si es mayor que π. Cada fuente o sumidero debe tener exactamente un ángulo grande, y cada vértice que no sea ni fuente ni sumidero no debe tener ninguno. Además, cada cara interna del dibujo debe tener dos ángulos pequeños más que grandes, y la cara externa debe tener dos ángulos grandes más que pequeños. Una asignación consistente es un etiquetado de los ángulos que satisface estas propiedades; cada incrustación ascendente tiene una asignación consistente. Por el contrario, cada grafo acíclico dirigido que tiene una incrustación plana bimodal con una asignación consistente tiene un dibujo plano ascendente, que puede construirse a partir de él en tiempo lineal. [3]

Otra caracterización es posible para los grafos con una única fuente. En este caso, una incrustación plana ascendente debe tener la fuente en la cara exterior, y cada ciclo no dirigido del grafo debe tener al menos un vértice en el que ambas aristas del ciclo sean entrantes (por ejemplo, el vértice con la posición más alta en el dibujo). Por el contrario, si una incrustación tiene ambas propiedades, entonces es equivalente a una incrustación ascendente. [4]

Complejidad computacional

Se sabe que son posibles varios casos especiales de pruebas de planaridad ascendente en tiempo polinomial :

Sin embargo, es NP-completo determinar si un gráfico acíclico dirigido planar con múltiples fuentes y sumideros tiene un dibujo planar ascendente. [17]

Dibujo de línea recta y requisitos de área

El teorema de Fáry establece que cada grafo plano tiene un dibujo en el que sus aristas están representadas por segmentos de línea recta, y lo mismo es cierto para el dibujo plano ascendente: cada grafo plano ascendente tiene un dibujo plano ascendente recto. [18] Un dibujo ascendente en línea recta de un grafo st -planar transitivamente reducido se puede obtener mediante la técnica de dibujo de dominancia , con todos los vértices teniendo coordenadas enteras dentro de una cuadrícula de n  ×  n . [19] Sin embargo, ciertos otros grafos planos ascendentes pueden requerir área exponencial en todos sus dibujos planos ascendentes en línea recta. [18] Si una elección de incrustación es fija, incluso los grafos paralelos en serie orientados y los árboles orientados pueden requerir área exponencial. [20]

Diagramas de Hasse

Los dibujos planares ascendentes son particularmente importantes para los diagramas de Hasse de conjuntos parcialmente ordenados , ya que normalmente se requiere que estos diagramas se dibujen ascendentemente. En términos de teoría de grafos, estos corresponden a los grafos acíclicos dirigidos transitivamente reducidos ; un grafo de este tipo se puede formar a partir de la relación de cobertura de un orden parcial, y el orden parcial en sí mismo forma la relación de alcanzabilidad en el grafo. Si un conjunto parcialmente ordenado tiene un elemento mínimo, tiene un elemento máximo y tiene un dibujo planar ascendente, entonces necesariamente debe formar una red , un conjunto en el que cada par de elementos tiene un único límite inferior máximo y un único límite superior mínimo. [21] El diagrama de Hasse de una red es planar si y solo si su dimensión de orden es como máximo dos. [22] Sin embargo, algunos órdenes parciales de dimensión dos y con un elemento mínimo y máximo no tienen un dibujo planar ascendente (tome el orden definido por el cierre transitivo de ).

Referencias

Notas al pie
  1. ^ Garg y Tamassia (1995); Di Battista et al. (1998).
  2. ^ Garg y Tamassia (1995), págs. 111-112; Di Battista et al. (1998), 6.1 "Inclusión en un gráfico st plano ", págs. 172-179; Di Battista y Tamassia (1988); Kelly (1987).
  3. ^ Garg y Tamassia (1995), págs. 112-115; Di Battista et al. (1998), 6.2 "Ángulos en dibujos ascendentes", págs. 180-188; Bertolazzi y Di Battista (1991); Bertolazzi et al. (1994).
  4. ^ Garg y Tamassia (1995), pág. 115; Di Battista et al. (1998), 6.7.2 "Ciclos prohibidos para dígrafos de fuente única", págs. 209-210; Thomassen (1989).
  5. ^ Garg y Tamassia (1995), pág. 119; Di Battista et al. (1998), pág. 179.
  6. ^ Garg y Tamassia (1995), págs. 119-121; Di Battista et al. (1998), 6.3 "Prueba de planaridad ascendente de dígrafos integrados", págs. 188-192; Bertolazzi y Di Battista (1991); Bertolazzi et al. (1994); Abbasi, Healy y Rextin (2010).
  7. ^ Di Battista y col. (1998), págs. 191-192; Bertolazzi y Di Battista (1991); Bertolazzi et al. (1994).
  8. ^ Garg y Tamassia (1995), págs. 125-126; Di Battista et al. (1998), 6.7.1 "Dígrafo plano exterior", pág. 209; Papakostas (1995).
  9. ^ abc Di Battista et al. (1998), 6.7.4 "Algunas clases de dígrafos planares ascendentes", pág. 212.
  10. ^ Didimo, Giordano y Liotta (2009).
  11. ^ Di Battista, Liu y rival (1990).
  12. ^ Garg y Tamassia (1995), págs. 122-125; Di Battista et al. (1998), 6.5 "Prueba de planaridad ascendente óptima de dígrafos de fuente única", págs. 195-200; Hutton y Lubiw (1996); Bertolazzi et al. (1998).
  13. ^ Chan (2004); Healy y Lynch (2006).
  14. ^ Healy y Lynch (2006).
  15. ^ Chaplick y otros (2022)
  16. ^ Jünger y Leipert (1999).
  17. ^ Garg y Tamassia (1995), págs. 126-132; Di Battista et al. (1998), 6.6 "La prueba de planaridad ascendente es NP-completa", págs. 201-209; Garg y Tamassia (2001).
  18. ^ ab Di Battista y Frati (2012); Di Battista, Tamassia y Tollis (1992).
  19. ^ Di Battista y col. (1998), 4.7 "Dibujos de dominancia", págs. 112-127; Di Battista, Tamassia y Tollis (1992).
  20. ^ Di Battista y Frati (2012); Bertolazzi et al. (1994); Frati (2008).
  21. ^ Di Battista y col. (1998), 6.7.3 "Estructuras prohibidas para celosías", págs. 210-212; Platón (1976).
  22. ^ Garg y Tamassia (1995), págs. 118; Baker, Fishburn y Roberts (1972).
Encuestas y libros de texto
Artículos de investigación