stringtranslate.com

Dibujo RAC

Dibujos RAC del grafo completo K 5 y del grafo bipartito completo K 3,4

En el dibujo de gráficos , un dibujo RAC de un gráfico es un dibujo en el que los vértices se representan como puntos, las aristas se representan 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 en ángulos rectos entre sí. En el nombre de este estilo de dibujo, "RAC" significa "cruce de ángulos rectos".

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

Ejemplos

El gráfico completo K 5 tiene un dibujo RAC con aristas rectas, pero K 6 no. Todo dibujo RAC de 6 vértices tiene como máximo 14 aristas, pero K 6 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 plano y (por el teorema de Fáry ) todo grafo plano tiene un dibujo de línea recta sin cruces. Un dibujo de este tipo 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 grafos siguientes, K 4,4 y K 3,5 , tiene un dibujo RAC. [4]

Bordes y curvas

Si un grafo de n vértices ( n ≥ 4) tiene un dibujo RAC con aristas rectas, puede tener como máximo 4 n  − 10 aristas. Esto es estricto: existen grafos dibujables RAC con exactamente 4 n  − 10 aristas. [1] Para los dibujos con aristas de polilínea, el límite en el número de aristas en el grafo depende del número de curvas que se permiten 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,5 n aristas [5] y con dos curvas hay como máximo 74,2 n aristas. [6] Cada grafo tiene un dibujo RAC con tres curvas por arista. [1]

Relación con la 1-planaridad

Un grafo es uniplanar si tiene un dibujo con como máximo un cruce por arista. Intuitivamente, esta restricción hace que sea más fácil hacer que este cruce sea en ángulos rectos, y el límite de 4 n  − 10 en el número de aristas de los dibujos RAC de línea recta es cercano a los límites de 4 n  − 8 en el número de aristas en un grafo uniplanar , y de 4 n  − 9 en el número de aristas en un grafo uniplanar de línea recta. Todo dibujo RAC con 4 n  − 10 aristas es uniplanar. [7] [8] Además, todo grafo uniplanar externo (es decir, un grafo dibujado con un cruce por arista con todos los vértices en la cara externa del dibujo) tiene un dibujo RAC. [9] Sin embargo, existen grafos uniplanares con 4 n  − 10 aristas que no tienen dibujos RAC. [7]

Complejidad computacional

Es NP-difícil determinar si un gráfico dado tiene un dibujo RAC con bordes rectos, [10] incluso si el gráfico 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 gráficos acíclicos dirigidos . [13] Sin embargo, en el caso especial de los gráficos 1-planares externos, se puede construir un dibujo RAC en tiempo lineal. [14]

Referencias

  1. ^ abcd Didimo, Walter; Eades, Peter ; Liotta, Giuseppe (2009), "Dibujar gráficos con cruces de ángulos rectos", Algorithms and Data Structures : 11th International Symposium, WADS 2009, Banff, Canadá, 21-23 de agosto de 2009. Actas , Lecture Notes in Computer Science , vol. 5664, págs. 206-217, doi :10.1007/978-3-642-03367-4_19, ISBN 978-3-642-03366-7.
  2. ^ Huang, Weidong; Hong, Seok-Hee ; Eades, Peter (2008), "Efectos de los ángulos cruzados", Simposio de visualización del IEEE del Pacífico (PacificVIS '08) , págs. 41–46, doi :10.1109/PACIFICVIS.2008.4475457, ISBN 978-1-4244-1966-1.
  3. ^ van Kreveld, Marc (2011), "La relación de calidad de los dibujos RAC y los dibujos planos de grafos planos", Graph Drawing : 18th International Symposium, GD 2010, Konstanz, Alemania, 21-24 de septiembre de 2010, Revised Selected Papers , Lecture Notes in Computer Science, vol. 6502, págs. 371-376, doi : 10.1007/978-3-642-18469-7_34 , ISBN 978-3-642-18468-0.
  4. ^ Didimo, Walter; Eades, Peter ; Liotta, Giuseppe (2010), "Una caracterización de gráficos RAC bipartitos completos", Information Processing Letters , 110 (16): 687–691, doi :10.1016/j.ipl.2010.05.023, MR  2676805.
  5. ^ Angelini, Patrizio; Bekos, Michael; Förster, Henry; Kaufmann, Michael (2018), Sobre dibujos RAC de gráficos con una curva por arista , arXiv : 1808.10470
  6. ^ Arikushi, Karin; Fulek, Radoslav; Keszegh, Balázs; Morić, Filip; Tóth, Csaba D. (2012), "Gráficos que admiten dibujos de cruce en ángulo recto", Teoría y aplicaciones de la geometría computacional , 45 (4): 169–177, arXiv : 1001.3117 , doi : 10.1016/j.comgeo.2011.11.008 , Señor  2876688.
  7. ^ ab Eades, Peter ; Liotta, Giuseppe (2013), "Gráficos que se cruzan en ángulos rectos y 1-planaridad", Discrete Applied Mathematics , 161 (7–8): 961–969, doi : 10.1016/j.dam.2012.11.019 , MR  3030582.
  8. ^ Ackerman, Eyal (2014), "Una nota sobre gráficos uniplanares", Discrete Applied Mathematics , 175 : 104–108, doi : 10.1016/j.dam.2014.05.025 , MR  3223912.
  9. ^ Dehkordi, Hooman Reisi; Eades, Peter (2012), "Todo gráfico del plano exterior 1 tiene un dibujo que cruza un ángulo recto", International Journal of Computational Geometry & Applications , 22 (6): 543–557, doi :10.1142/S021819591250015X, MR  3042921.
  10. ^ Argyriou, Evmorfia N.; Bekos, Michael A.; Symvonis, Antonios (2011), "El problema del dibujo de RAC en línea recta es NP-duro", SOFSEM 2011: 37.ª Conferencia sobre tendencias actuales en teoría y práctica de la informática, Nový Smokovec, Eslovaquia, 22-28 de enero de 2011, Actas , Lecture Notes in Computer Science, vol. 6543, págs. 74–85, arXiv : 1009.5227 , Bibcode :2011LNCS.6543...74A, doi :10.1007/978-3-642-18381-2_6, ISBN 978-3-642-18380-5
  11. ^ Bekos, Michael A.; Didimo, Walter; Liotta, Giuseppe; Mehrabi, Saeed; Montecchiani, Fabrizio (2017), "Sobre los dibujos RAC de gráficos uniplanares", Theoretical Computer Science , 689 : 48–57, arXiv : 1608.08418 , doi :10.1016/j.tcs.2017.05.039
  12. ^ Schaefer, Marcus (2021), "RAC-drawability is -complete", Actas del 29º Simposio Internacional sobre Dibujo de Gráficos y Visualización de Redes (GD 2021) , arXiv : 2107.11663
  13. ^ Angelini, Patrizio; Cittadini, Luca; Di Battista, Giuseppe; Didimo, Walter; Frati, Fabrizio; Kaufmann, Michael; Symvonis, Antonios (2010), "Sobre las perspectivas abiertas por dibujos de cruces de ángulos rectos", Graph Drawing : 17th International Symposium, GD 2009, Chicago, IL, EE. UU., 22-25 de septiembre de 2009, Documentos revisados , Lecture Notes in Computer Science, vol. 5849, págs. 21-32, doi : 10.1007/978-3-642-11805-0_5 , ISBN 978-3-642-11804-3.
  14. ^ Auer, Cristóbal; Bachmaier, cristiano; Brandeburgo, Franz J.; Hanauer, Kathrin; Gleissner, Andreas; Neuwirth, Daniel; Reislhuber, Josef (2013), "Reconocimiento de gráficos uniplanares externos en tiempo lineal", Dibujo de gráficos LNCS , Apuntes de conferencias sobre informática, 8284 : 107–118, doi :10.1007/978-3-319-03841-4, ISBN 978-3-319-03840-7