Representación plana ascendente

Una representación plana ascendente de un gráfico acíclico dirigido  es una incrustación del gráfico en el espacio euclidiano , en el que los bordes se representan como curvas monótonamente crecientes que no se cruzan . Es decir, una curva que representa cualquier arista debe tener la propiedad de que cualquier línea horizontal la intersecta como máximo en un punto, y dos aristas no pueden intersecarse excepto en los extremos [1] [2] . En este sentido, es un caso ideal para el dibujo de gráficos en capas , un estilo de representación de gráficos en el que las curvas monótonas pueden cruzarse, pero en el que el número de intersecciones es mínimo.

Descripciones

Un gráfico acíclico dirigido debe ser plano para tener una representación plana ascendente, pero no todos los gráficos acíclicos planos tienen tal representación. Entre todos los grafos acíclicos planos dirigidos con una sola fuente (un vértice que no tiene arcos entrantes) y un sumidero (un vértice que no tiene arcos salientes), los grafos con representaciones planares ascendentes son grafos st -planares , grafos planos en los que la fuente y fregadero pertenecen a la misma y la misma cara para al menos una incrustación de gráfico plano. Más generalmente, un grafo G tiene una representación plana ascendente si y solo si es dirigido, acíclico y es un subgrafo de un grafo st -planar en el mismo conjunto de vértices [3] [4] [5] [6] .

En un anidamiento ascendente, el conjunto de arcos entrantes y salientes incidentes en cada vértice siguen en sucesión en el orden cíclico de los arcos en el vértice. Se dice que una incrustación plana de un gráfico acíclico dirigido dado es bimodal si tiene esta propiedad. Además, el ángulo entre dos arcos consecutivos con la misma orientación en un vértice dado se puede etiquetar como pequeño si es menor que , o grande si es mayor que . Cada sumidero debe tener exactamente un ángulo grande, y cualquier vértice que no sea fuente ni sumidero no debe tener un ángulo grande. Además, cada cara interior de la representación debe tener dos ángulos menores más que ángulos mayores, y la cara exterior debe tener dos ángulos mayores más que ángulos menores. La asignación correcta  es el marcado de las esquinas, que cumple las propiedades descritas. Cualquier archivo adjunto aguas arriba tiene un propósito válido. Por el contrario, cualquier gráfico acíclico dirigido que tenga una incrustación plana bimodal con la asignación correcta tiene una representación plana ascendente que se puede construir en tiempo lineal [7] [8] [9] [10] .

Otra descripción es posible para gráficos con una sola fuente. En este caso, la incrustación plana hacia arriba debe originarse en la cara exterior, y cualquier ciclo no dirigido en el gráfico debe tener al menos un vértice en el que ambos arcos del ciclo estén llegando (por ejemplo, el vértice en la parte superior de la figura). ). Por el contrario, si una incrustación tiene ambas propiedades, entonces es equivalente a una incrustación ascendente [11] [12] [13] .

Complejidad computacional

Se sabe que algunos casos especiales de comprobación de planaridad ascendente se pueden realizar en tiempo polinomial :

Sin embargo, el problema de determinar si un gráfico acíclico dirigido plano multifuente y multisumidero tiene una representación plana ascendente es NP-completo [33] [34] [35] .

Dibujo lineal y requisitos de área

El teorema de Fari establece que cualquier gráfico plano tiene una representación en la que los bordes están representados por segmentos de línea, y lo mismo es cierto para una representación plana ascendente: cualquier gráfico plano ascendente tiene una representación plana ascendente con arcos en forma de segmentos de línea [36 ] [37] . Se puede obtener una representación rectilínea ascendente de un grafo st -planar transitivamente reducido utilizando la técnica de dibujo dominante con todos los vértices que tienen coordenadas enteras en la red [38] [37] . Sin embargo, algunos otros gráficos planos ascendentes pueden requerir un área exponencial para todas sus representaciones planas ascendentes rectilíneas [36] [37] . Si la incrustación es fija, incluso los gráficos en serie paralelos dirigidos y los árboles dirigidos pueden requerir un área exponencial [36] [39] [40] .

Diagramas de Hasse

Las representaciones planas ascendentes son especialmente importantes para los diagramas de Hasse de conjuntos parcialmente ordenados , ya que estos diagramas generalmente deben dibujarse en un estilo ascendente. En términos de teoría de grafos, esto corresponde a grafos acíclicos dirigidos transitivamente reducidos . Tal gráfico se puede formar a partir de una relación de orden parcial de cobertura, y el propio orden parcial forma una relación de accesibilidad en el gráfico. Si un poset tiene un elemento mínimo, tiene un elemento máximo y tiene una representación plana ascendente, necesariamente forma una red , un conjunto en el que cualquier par de elementos tiene un solo límite inferior mayor y un solo límite superior más pequeño [41] [ 42] . El diagrama de Hasse de una red es plano si y solo si su dimensión ordinal no excede de dos [43] [44] . Sin embargo, algunos órdenes parciales de dimensión dos con elementos mínimo y máximo no tienen una representación plana ascendente (tomamos el orden definido por la clausura transitiva del orden ).

Notas

  1. ↑ Garg, Tamassia, 1995 .
  2. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 .
  3. ↑ Garg, Tamassia, 1995 , pág. 111–112.
  4. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 172–179, §6.1 Inclusión en un Planarst -Graph.
  5. ↑ Di Battista, Tamassia, 1988 .
  6. ↑ Kelly, 1987 .
  7. ↑ Garg, Tamassia, 1995 , pág. 112–115.
  8. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 180–188, §6.2 Ángulos en dibujos ascendentes.
  9. ↑ 1 2 3 Bertolazzi, Di Battista, 1991 .
  10. ↑ 1 2 3 Bertolazzi, Di Battista, Liotta, Mannino, 1994 .
  11. ↑ Garg, Tamassia, 1995 , pág. 115.
  12. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 209–210, §6.7.2 Ciclos prohibidos para dígrafos de fuente única.
  13. ↑ Thomassen, 1989 .
  14. ↑ Garg, Tamassia, 1995 , pág. 119.
  15. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 179.
  16. ↑ Garg, Tamassia, 1995 , pág. 119–121.
  17. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 188–192, §6.3 Prueba de planaridad ascendente de dígrafos incrustados.
  18. ↑ Abbasi, Healy, Rextin, 2010 .
  19. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 191–192.
  20. ↑ Garg, Tamassia, 1995 , pág. 125–126.
  21. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 209, §6.7.1 Dígrafo exterior.
  22. ↑ Papakostas, 1995 .
  23. ↑ 1 2 3 Di Battista, Eades, Tamassia, Tollis, 1998 , p. 212, §6.7.4 Algunas clases de dígrafos planos ascendentes.
  24. ↑ Dídimo, Giordano, Liotta, 2009 .
  25. ↑ Di Battista, Liu, Rival, 1990 .
  26. ↑ Garg, Tamassia, 1995 , pág. 122–125.
  27. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 195–200, §6.5 Prueba óptima de planaridad ascendente de dígrafos de fuente única.
  28. ↑ Hutton, Lubiw, 1996 .
  29. ↑ Bertolazzi, Di Battista, Mannino, Tamassia, 1998 .
  30. ↑ Chan, 2004 .
  31. ↑ 12Healy , Lynch , 2006 .
  32. ↑ Junger, Leipert, 1999 .
  33. ↑ Garg, Tamassia, 1995 , pág. 126–132.
  34. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 201–209, §6.6 La prueba de planaridad ascendente es NP completa.
  35. ↑ Garg, Tamassia, 2001 .
  36. ↑ 1 2 3 Di Battista, Frati, 2012 , p. 149–151, §5 Dibujos ascendentes.
  37. ↑ 1 2 3 Di Battista, Tamassia, Tollis, 1992 .
  38. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 112–127 §4.7 Dibujos de Dominancia.
  39. ↑ Bertolazzi, Cohen, Di Battista, Tamassia, Tollis, 1994 .
  40. ↑ Fratti, 2008 .
  41. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 210–212 §6.7.3 Estructuras prohibidas para celosía.
  42. ↑ Platt, 1976 .
  43. ↑ Garg, Tamassia, 1995 , pág. 118.
  44. ↑ Panadero, Fishburn, Roberts, 1972 .

Literatura

Reseñas y Tutoriales Trabajo de investigación