En los estilos de dibujo de gráficos que representan los bordes de un gráfico mediante polilíneas (secuencias de segmentos de línea conectados en las curvas ), es deseable minimizar el número de curvas por borde (a veces llamado complejidad de la curva ) [1] o el número total de curvas. en un dibujo. [2] La minimización de pliegues es el problema algorítmico de encontrar un dibujo que minimice estas cantidades. [3] [4]
Eliminando todas las curvas
El ejemplo prototípico de minimización de curvas es el teorema de Fáry , que establece que cada gráfico plano se puede dibujar sin curvas, es decir, con todos sus bordes dibujados como segmentos de línea recta. [5]
Los dibujos de un gráfico en el que los bordes no tienen dobleces y están alineados con el eje a veces se denominan dibujos rectilíneos y son una forma de construir dibujos RAC en los que todos los cruces están en ángulos rectos. [6] Sin embargo, es NP-completo para determinar si un gráfico plano tiene un dibujo rectilíneo plano, [7] y NP-completo para determinar si un gráfico arbitrario tiene un dibujo rectilíneo que permite cruces. [6]
Minimización de pliegues
Tamassia (1987) mostró que la minimización de la curvatura de los dibujos ortogonales de gráficos planos, en los que los vértices se colocan en una celosía entera y los bordes se dibujan como polilíneas alineadas con el eje, podría realizarse en tiempo polinomial traduciendo el problema a uno de mínimos. -Flujo de red de costes . [8] [9] Sin embargo, si se puede cambiar la incrustación plana del gráfico, entonces la minimización de plegado se convierte en NP-completo y, en su lugar, debe resolverse mediante técnicas como la programación de enteros que no garantizan un tiempo de ejecución rápido y una respuesta exacta. . [10]
Pocas curvas por borde
Muchos estilos de dibujo de gráficos permiten pliegues, pero solo de forma limitada: la complejidad de la curva de estos dibujos (el número máximo de pliegues por borde) está limitada por alguna constante fija. Permitir que esta constante crezca más se puede utilizar para mejorar otros aspectos del dibujo, como su área . [1] Alternativamente, en algunos casos, un estilo de dibujo solo puede ser posible cuando se permiten curvas; por ejemplo, no todos los gráficos tienen un dibujo RAC (un dibujo con todos los cruces en ángulos rectos) sin curvas, o con una complejidad de curva dos, pero cada gráfico tiene un dibujo con una complejidad de curva tres. [11]
Referencias
- ↑ a b Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe; Meijer, Henk (2011), "Área, complejidad de la curva y resolución de cruce de dibujos de gráficos no planos", Teoría de los sistemas informáticos , 49 (3): 565–575, doi : 10.1007 / s00224-010-9275-6 , Señor 2822838.
- ^ Di Battista, Giuseppe; Eades, Peter ; Tamassia, Roberto ; Tollis, Ioannis G. (1998), Dibujo de gráficos: algoritmos para la visualización de gráficos (1ª ed.), Prentice Hall, págs. 15-16, ISBN 978-0133016154.
- ^ Di Battista y col. (1998) , pág. 145.
- ^ Purchase, Helen (1997), "¿Qué estética tiene el mayor efecto en la comprensión humana?", Dibujo gráfico: 5to Simposio Internacional, GD '97 Roma, Italia, 18-20 de septiembre de 1997, Actas , Notas de conferencia en Ciencias de la Computación , 1353 , págs. 248–261, doi : 10.1007 / 3-540-63938-1_67 , ISBN 978-3-540-63938-1.
- ^ Di Battista y col. (1998) , pág. 140.
- ^ a b Eades, Peter ; Hong, Seok-Hee; Poon, Sheung-Hung (2010), "On rectilinear drawing of graphs", Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, 22-25 de septiembre de 2009, Revised Papers , Lecture Notes in Computer Science, 5849 , Springer, págs. 232–243, doi : 10.1007 / 978-3-642-11805-0_23 , ISBN 978-3-642-11804-3, MR 2680455.
- ^ Garg, Ashim; Tamassia, Roberto (2001), "Sobre la complejidad computacional de las pruebas de planaridad ascendente y rectilínea", SIAM Journal on Computing , 31 (2): 601–625, doi : 10.1137 / S0097539794277123 , MR 1861292.
- ^ Tamassia, Roberto (1987), "Sobre la inserción de un gráfico en la cuadrícula con el número mínimo de curvas", SIAM Journal on Computing , 16 (3): 421–444, doi : 10.1137 / 0216030 , MR 0889400.
- ^ Cornelsen, Sabine; Karrenbauer, Andreas (2012), "Reducción al mínimo de curvatura acelerada", Journal of Graph Algorithms and Applications , 16 (3): 635–650, doi : 10.7155 / jgaa.00265 , MR 2983428.
- ^ Mutzel, Petra ; Weiskircher, René (2002), "Minimización de curvas en dibujos ortogonales usando programación de números enteros", Computación y combinatoria: 8a Conferencia Internacional Anual, COCOON 2002, Singapur, 15-17 de agosto de 2002, Actas , Lecture Notes in Computer Science, 2387 , págs. . 484–493, CiteSeerX 10.1.1.138.1513 , doi : 10.1007 / 3-540-45655-4_52 , ISBN 978-3-540-43996-7.
- ^ Didimo, Walter; Eades, Peter ; Liotta, Giuseppe (2009), "Dibujar gráficos con cruces en ángulo recto", Algoritmos y estructuras de datos: 11th International Symposium, WADS 2009, Banff, Canadá, 21-23 de agosto de 2009. Actas , Lecture Notes in Computer Science, 5664 , págs. 206–217, doi : 10.1007 / 978-3-642-03367-4_19 , ISBN 978-3-642-03366-7.