Minimización de torceduras

Al visualizar gráficos , cuando los bordes del gráfico están representados por líneas quebradas (una secuencia de segmentos conectados en puntos de ruptura ), es deseable minimizar el número de rupturas por borde (a veces llamado complejidad de la curva ) [1] o el número total de rupturas en la figura [2] . La minimización de torceduras es una tarea algorítmica de encontrar un patrón gráfico que minimice los valores especificados [3] [4] .

Exclusión de torceduras

Un ejemplo clásico de minimización de torceduras es el teorema de Fari , que establece que cualquier gráfico plano se puede dibujar sin torceduras, es decir, puede encontrar un gráfico plano incrustado en el que todos los bordes estarán representados por segmentos [5] .

Una representación gráfica en la que los bordes no tienen torceduras y son paralelos a los ejes a veces se denomina representación rectangular y es una de las variantes de la representación de intersección de bordes ortogonales , en la que todas las intersecciones de bordes ocurren en ángulos rectos [6] . Sin embargo, determinar si un gráfico plano tiene una representación rectangular es un problema NP-completo [7] . También es un problema NP-completo determinar si un gráfico arbitrario tiene una representación rectangular dadas las intersecciones de los bordes [6] .

Minimización de torceduras

Tamassia demostró que la minimización de las torceduras en un patrón ortogonal de gráficos planos, en los que los vértices se ubican en los nodos de una red de enteros y los bordes se dibujan como líneas quebradas que consisten en segmentos paralelos a los ejes, se puede llevar a cabo en polinomio. tiempo transfiriendo el problema al problema de encontrar el flujo de costo mínimo [8 ] [9] . Sin embargo, si cambiamos la forma en que se incrusta el gráfico planar, el problema de minimización de torceduras se convierte en NP-completo y debe resolverse mediante métodos como la programación entera , que no garantiza una solución precisa ni una operación rápida [10] .

Varias torceduras por borde

Muchos estilos de dibujo de gráficos permiten torceduras, pero de forma limitada, la complejidad de la curva de estas representaciones (el número máximo de torceduras por borde) está limitada a alguna constante. Permitir que esta constante crezca se puede usar para mejorar otras características del dibujo, como el área [1] . En algunos casos, el estilo solo puede ser posible cuando se resuelven los jogs. Por ejemplo, no todos los gráficos tienen una representación con intersección de bordes ortogonales sin torceduras, o con complejidad de curva dos, pero cualquier gráfico tiene un patrón de este tipo con complejidad de curva tres [11] .

Notas

  1. ↑ 1 2 Di Giacomo, Didimo, Liotta, Meijer, 2011 , p. 565–575.
  2. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 15–16.
  3. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 145.
  4. ↑ Compra, 1997 , p. 248–261.
  5. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 140.
  6. ↑ 1 2 Eades, Hong, Poon, 2010 , pág. 232–243.
  7. ↑ Garg, Tamassia, 2001 , pág. 601–625.
  8. ↑ Tamassia, 1987 , pág. 421–444.
  9. ↑ Cornelsen, Karrenbauer, 2012 , pág. 635–650.
  10. ↑ Mutzel, Weiskircher, 2002 , pág. 484–493.
  11. ↑ Didimo, Eades, Liotta, 2009 , pág. 206–217.

Literatura