Minimización de curvaturas

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 curvas ), es deseable minimizar la cantidad de curvas por borde (a veces llamada complejidad de curva ) ^[1] o la cantidad total de curvas en un dibujo. ^[2] La minimización de curvas es el problema algorítmico de encontrar un dibujo que minimice estas cantidades. ^{[3] [4]}

El ejemplo prototípico de minimización de curvaturas es el teorema de Fáry , que establece que todo grafo plano puede dibujarse sin curvas, es decir, con todos sus bordes dibujados como segmentos de línea recta. ^[5]

Los dibujos de un gráfico en los que los bordes no tienen curvaturas 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 determinar si un gráfico plano tiene un dibujo rectilíneo plano, ^[7] y NP-completo determinar si un gráfico arbitrario tiene un dibujo rectilíneo que permite cruces. ^[6]

Tamassia (1987) demostró que la minimización de curvaturas en dibujos ortogonales de grafos planares, en los que los vértices se colocan en una red entera y los bordes se dibujan como polilíneas alineadas con el eje, se podría realizar en tiempo polinomial traduciendo el problema a uno de flujo de red de costo mínimo . ^{[8] [9]} Sin embargo, si se puede cambiar la incrustación plana del grafo, entonces la minimización de curvaturas se vuelve NP-completa y, en cambio, debe resolverse mediante técnicas como la programación entera que no garantizan tanto un tiempo de ejecución rápido como una respuesta exacta. ^[10]

Muchos estilos de dibujo de gráficos permiten curvas, pero sólo de forma limitada: la complejidad de la curva de estos dibujos (el número máximo de curvas por arista) está limitada por una constante fija. Permitir que esta constante crezca puede utilizarse para mejorar otros aspectos del dibujo, como su área . ^[1] Alternativamente, en algunos casos, un estilo de dibujo sólo 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 todos los gráficos tienen un dibujo de este tipo con una complejidad de curva tres. ^[11]