Plano RAC

En el dibujo de grafos , un dibujo RAC es aquel en el que los vértices se representan como puntos, las aristas como segmentos de línea recta o polilíneas , como máximo dos aristas se cruzan en cualquier punto, y cuando dos aristas se cruzan, lo hacen formando un ángulo recto entre sí. En el nombre de este estilo de dibujo, "RAC" significa "cruce en ángulo recto".

El estilo de cruce en ángulo recto y el nombre "dibujo RAC" para este estilo fueron formulados por Didimo, Eades y Liotta (2009) , ^{[ 1 ]} motivados por estudios de usuarios previos que mostraron que los cruces con ángulos grandes son mucho menos perjudiciales para la legibilidad de los dibujos que los cruces poco profundos. ^{[ 2 ]} Incluso para gráficos planares , permitir algunos cruces en ángulo recto en un dibujo del gráfico puede mejorar significativamente medidas de la calidad del dibujo, como su área o resolución angular . ^{[ 3 ]}

El grafo completo K ₅ tiene un dibujo RAC con aristas rectas, pero K ₆ no. Todo dibujo RAC de 6 vértices tiene como máximo 14 aristas, pero K ₆ tiene 15 aristas, demasiadas para tener un dibujo RAC. ^{[ 1 ]}

Un grafo bipartito completo K _{a , b} tiene un dibujo RAC con aristas rectas si y solo si min( a , b )  ≤  2 o a  + b ≤ 7. Si min( a , b ) ≤ 2, entonces el grafo es un grafo planar y (por el teorema de Fáry ) todo grafo planar tiene un dibujo de líneas rectas sin cruces. Dicho dibujo es automáticamente un dibujo RAC. Los únicos dos casos restantes son los grafos K _3,3 y K _3,4 . Se muestra un dibujo de K _3,4 ; K _3,3 se puede formar a partir de él eliminando un vértice. Ninguno de los dos siguientes grafos más grandes, K _4,4 y K _3,5 , tiene un dibujo RAC. ^{[ 4 ]}     

Si un grafo de n vértices ( n ≥ 4) tiene un dibujo RAC con aristas rectas, puede tener como máximo 4n −  10  aristas. Esto es estricto: existen grafos dibujables con RAC con exactamente 4n −  10  aristas. ^{[ 1 ]} Para dibujos con aristas de polilínea, el límite en el número de aristas en el grafo depende del número de curvas permitidas por arista. Los grafos que tienen dibujos RAC con una o dos curvas por arista tienen O( n ) aristas; más específicamente, con una curva hay como máximo 5,5n aristas [ ^{5 ] y} con dos curvas hay como máximo 74,2n aristas . ^{[ 6 ]} Todo grafo tiene un dibujo RAC con tres curvas por arista. ^{[ 1 ]}

Un grafo es 1-planar si tiene un dibujo con como máximo un cruce por arista. Intuitivamente, esta restricción facilita que este cruce sea en ángulo recto, y el límite de 4 n  −  10 en el número de aristas de los dibujos RAC de línea recta está cerca de los límites de 4 n  −  8 en el número de aristas en un grafo 1-planar , y de 4 n  −  9 en el número de aristas en un grafo 1-planar de línea recta. Todo dibujo RAC con 4 n  −  10 aristas es 1-planar. ^{[ 7 ] [ 8 ]} Además, todo grafo exterior 1-planar (es decir, un grafo dibujado con un cruce por arista con todos los vértices en la cara exterior del dibujo) tiene un dibujo RAC. ^{[ 9 ]} Sin embargo, existen grafos 1-planares con 4 n  −  10 aristas que no tienen dibujos RAC. ^{[ 7 ]}

Es NP-difícil determinar si un grafo dado tiene un dibujo RAC con aristas rectas, ^{[ 10 ]} incluso si el grafo de entrada es 1-planar y el dibujo RAC de salida también debe ser 1-planar. ^{[ 11 ]} Más específicamente, el dibujo RAC es completo para la teoría existencial de los reales . ^{[ 12 ]} El problema del dibujo RAC sigue siendo NP-difícil para el dibujo ascendente de grafos acíclicos dirigidos . ^{[ 13 ]} Sin embargo, en el caso especial de grafos 1-planares externos, un dibujo RAC puede construirse en tiempo lineal. ^{[ 14 ]}