En el dibujo de un gráfico , 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 en ángulo recto".
El estilo de cruce en ángulo recto y el nombre "dibujo RAC" para este estilo fueron ambos formulados por Didimo, Eades & Liotta (2009) , [1] motivados por estudios de usuarios anteriores que muestran que los cruces con ángulos grandes son mucho menos dañinos para la legibilidad de dibujos que de cruces superficiales. [2] Incluso para gráficos planos , permitir algunos cruces en ángulo recto 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 de
El gráfico completo K 5 tiene un dibujo RAC con bordes rectos, pero K 6 no. Cada 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 gráfico bipartito completo K a , b tiene un dibujo RAC con bordes rectos si y solo si min ( a , b ) ≤ 2 o a + b ≤ 7. Si min ( a , b ) ≤ 2, entonces el gráfico es un gráfico plano , y (según el teorema de Fáry ) cada gráfico plano tiene un dibujo de línea recta sin cruces. Dicho dibujo es automáticamente un dibujo RAC. Los únicos dos casos que quedan son los gráficos 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 siguientes dos gráficos más grandes, K 4,4 y K 3,5 , tiene un dibujo RAC. [4]
Bordes y curvas
Si un gráfico de n -vértices tiene un dibujo RAC con bordes rectos, puede tener como máximo 4 n - 10 bordes. Esto es estrecho: existen gráficos dibujables por RAC con exactamente 4 n - 10 bordes. [1] Para dibujos con bordes de polilínea, el límite del número de bordes en el gráfico depende del número de pliegues permitidos por borde. Los gráficos que tienen dibujos RAC con una o dos curvas por borde tienen O ( n ) bordes; más específicamente, con una curva hay como máximo 5,5 n bordes [5] y con dos curvas hay como máximo 74,2 n bordes. [6] Cada gráfico tiene un dibujo RAC con tres curvas por borde. [1]
Relación con 1-planaridad
Un gráfico es 1 plano si tiene un dibujo con como máximo un cruce por borde. 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 bordes de los dibujos RAC en línea recta está cerca de los límites de 4 n - 8 en el número de bordes. en un gráfico de 1 plano , y de 4 n - 9 en el número de aristas en un gráfico de 1 plano de línea recta. Cada dibujo RAC con 4 n - 10 aristas es 1 plano. [7] [8] Además, cada gráfico exterior 1 plano (es decir, un gráfico dibujado con un cruce por borde con todos los vértices en la cara exterior del dibujo) tiene un dibujo RAC. [9] Sin embargo, existen gráficos de 1 plano 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-plano y el dibujo RAC de salida debe ser también 1-plano. [11] El problema de dibujo RAC sigue siendo NP-difícil para el dibujo ascendente de gráficos acíclicos dirigidos . [12] Sin embargo, en el caso especial de las gráficas planas exteriores 1, se puede construir un dibujo RAC en tiempo lineal. [13]
Referencias
- ^ a b c d 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 al 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.
- ^ Huang, Weidong; Hong, Seok-Hee; Eades, Peter (2008), "Efectos de los ángulos cruzados ", IEEE Pacific Visualization Symposium (PacificVIS '08) , págs. 41–46, doi : 10.1109 / PACIFICVIS.2008.4475457.
- ^ van Kreveld, Marc (2011), "The quality ratio of RAC drawings and planar drawings of planar graphs", Graph Drawing : 18th International Symposium, GD 2010, Konstanz, Germany, 21-24 de septiembre de 2010, Revised Selected Papers , Lecture Notes en Ciencias de la Computación, 6502 , págs. 371–376, doi : 10.1007 / 978-3-642-18469-7_34.
- ^ 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.
- ^ Angelini, Patrizio; Bekos, Michael; Förster, Henry; Kaufmann, Michael (2018), sobre dibujos de gráficos RAC con un pliegue por borde , arXiv : 1808.10470
- ^ Arikushi, Karin; Fulek, Radoslav; Keszegh, Balázs; Morić, Filip; Tóth, Csaba D. (2012), "Gráficos que admiten dibujos cruzados en ángulo recto", Teoría y aplicaciones de geometría computacional , 45 (4): 169-177, arXiv : 1001.3117 , doi : 10.1016 / j.comgeo.2011.11.008 , Señor 2876688.
- ^ a b Eades, Peter ; Liotta, Giuseppe (2013), "Gráficos cruzados en ángulo recto y 1-planaridad", Matemáticas aplicadas discretas , 161 (7–8): 961–969, doi : 10.1016 / j.dam.2012.11.019 , MR 3030582.
- ^ Ackerman, Eyal (2014), "A note on 1-planar graphs", Discrete Applied Mathematics , 175 : 104-108, doi : 10.1016 / j.dam.2014.05.025 , MR 3223912.
- ^ Dehkordi, Hooman Reisi; Eades, Peter (2012), "Cada gráfico de un plano exterior tiene un dibujo de cruce en ángulo recto", International Journal of Computational Geometry & Applications , 22 (6): 543–557, doi : 10.1142 / S021819591250015X , MR 3042921.
- ^ Argyriou, Evmorfia N .; Bekos, Michael A .; Symvonis, Antonios (2011), "El problema de dibujo de RAC en línea recta es NP-hard", SOFSEM 2011: 37th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Eslovaquia, 22-28 de enero de 2011, Actas , Lecture Notes in Computer Science, 6543 , págs. 74–85, arXiv : 1009.5227 , Bibcode : 2011LNCS.6543 ... 74A , doi : 10.1007 / 978-3-642-18381-2_6
- ^ Bekos, Michael A .; Didimo, Walter; Liotta, Giuseppe; Mehrabi, Saeed; Montecchiani, Fabrizio (2017), "Sobre dibujos RAC de gráficos 1-planar", Informática teórica , 689 : 48–57, arXiv : 1608.08418 , doi : 10.1016 / j.tcs.2017.05.039
- ^ Angelini, Patrizio; Cittadini, Luca; Di Battista, Giuseppe; Didimo, Walter; Frati, Fabrizio; Kaufmann, Michael; Symvonis, Antonios (2010), "Sobre las perspectivas abiertas por dibujos cruzados en ángulo recto", Dibujo gráfico : 17º Simposio Internacional, GD 2009, Chicago, IL, EE. UU., 22 al 25 de septiembre de 2009, Artículos revisados , Notas de conferencias en Ciencias de la Computación , 5849 , págs. 21–32, doi : 10.1007 / 978-3-642-11805-0_5.
- ^ Auer, Christopher; Bachmaier, Christian; Brandeburgo, Franz J .; Hanauer, Kathrin; Gleißner, Andreas; Neuwirth, Daniel; Reislhuber, Josef (2013). "Reconocimiento de gráficos 1-planar externos en tiempo lineal". Gráfico de dibujo LNCS . 8284 : 107-118. doi : 10.1007 / 978-3-319-03841-4 .