En el dibujo de gráficos , un diseño circular es un estilo de dibujo que coloca los vértices de un gráfico en un círculo , a menudo espaciados uniformemente para que formen los vértices de un polígono regular .
Aplicaciones
Los diseños circulares se adaptan bien a las topologías de redes de comunicaciones , como las redes en estrella o en anillo , [1] y para las partes cíclicas de las redes metabólicas . [2] Para gráficos con un ciclo hamiltoniano conocido , un diseño circular permite representar el ciclo como el círculo y, de esta manera, los diseños circulares forman la base de la notación LCF para gráficos cúbicos hamiltonianos . [3]
Un diseño circular puede usarse por sí solo para un dibujo de gráfico completo, pero también puede usarse como diseño para grupos más pequeños de vértices dentro de un dibujo de gráfico más grande, como sus componentes biconectados , [4] grupos de genes en un gen. gráfico de interacción, [5] o subgrupos naturales dentro de una red social . [6] Si se utilizan varios círculos de vértices de esta manera, se pueden utilizar otros métodos, como el dibujo de gráficos dirigidos por la fuerza, para organizar los grupos. [7]
Una ventaja de un diseño circular en algunas de estas aplicaciones, como la bioinformática o la visualización de redes sociales, es su neutralidad: [8] al colocar todos los vértices a distancias iguales entre sí y desde el centro del dibujo, ninguno tiene un privilegio posición, contrarrestando la tendencia de los espectadores a percibir los nodos ubicados más centralmente como más importantes. [9]
Estilo de borde
Los bordes del dibujo pueden representarse como cuerdas del círculo, [10] como arcos circulares [11] (posiblemente perpendiculares al círculo del vértice, de modo que los bordes modelen las líneas del modelo de disco de Poincaré de geometría hiperbólica ), o como tipos de curva. [12]
La distinción visual entre el interior y el exterior del círculo de vértice en un diseño circular se puede utilizar para separar dos estilos diferentes de dibujo de bordes. Por ejemplo, un algoritmo de dibujo circular de Gansner y Koren (2007) utiliza el agrupamiento de bordes dentro del círculo, junto con algunos bordes que no están agrupados, dibujados fuera del círculo. [12]
Para diseños circulares de gráficos regulares , con bordes dibujados tanto dentro como fuera como arcos circulares , el ángulo de incidencia de uno de estos arcos con el círculo del vértice es el mismo en ambos extremos del arco, una propiedad que simplifica la optimización del ángulo. resolución del dibujo. [11]
Numero de cruces
Varios autores han estudiado el problema de encontrar una permutación de los vértices de un diseño circular que minimice el número de cruces de aristas cuando todas las aristas se dibujan dentro del círculo de vértices. Este número de cruces es cero solo para gráficos planos exteriores . [13] Para otros gráficos, se puede optimizar o reducir por separado para cada componente biconectado del gráfico antes de combinar las soluciones, ya que estos componentes se pueden dibujar de manera que no interactúen. [14]
En general, minimizar el número de cruces es NP-completo , [15] pero puede aproximarse con una relación de aproximación de O (log 2 n ) donde n es el número de vértices. [16] También se han ideado métodos heurísticos para reducir la complejidad de los cruces, basados, por ejemplo, en un orden de inserción de vértices cuidadoso y en la optimización local . [17]
También se puede utilizar un diseño circular para maximizar el número de cruces. En particular, la elección de una permutación aleatoria para los vértices hace que cada posible cruce ocurra con una probabilidad de 1/3, por lo que el número esperado de cruces está dentro de un factor de tres del número máximo de cruces entre todos los diseños posibles. La aleatorización de este método proporciona un algoritmo de aproximación determinista con una relación de aproximación de tres. [18]
Otros criterios de optimización
Junto con los cruces, también se han desarrollado versiones circulares de problemas de optimización de las longitudes de los bordes en un diseño circular, la resolución angular de los cruces o el ancho de corte (el número máximo de bordes que conecta un arco del círculo con el arco opuesto). considerado, [19] pero muchos de estos problemas son NP-completos. [20]
Ver también
- Diagrama de acordes , un concepto estrechamente relacionado en la visualización de información
- Planaridad , un rompecabezas en el que un jugador debe mover vértices para desenredar un dibujo de un gráfico plano , a partir de un diseño circular aleatorio.
Notas
- ^ Doğrusöz, Madden y Madden (1997) .
- ^ Becker y Rojas (2001) .
- ^ Pisanski y Servatius (2013) .
- ^ Doğrusöz, Madden y Madden (1997) ; Six y Tollis (1999b) .
- ^ Symeonidis y Tollis (2004) .
- ^ Krebs (1996) .
- ^ Doğrusöz, Belviranli y Dilek (2012) .
- ^ Iragne y col. (2005) .
- ^ Huang, Hong y Eades (2007) .
- ^ Six y Tollis (1999a) .
- ^ a b Duncan y col. (2012) .
- ↑ a b Gansner y Koren (2007) .
- ^ Six y Tollis (1999a) ; Baur y Brandes (2005) .
- ^ Baur y Brandes (2005) .
- ^ Masuda y col. (1987) .
- ^ Shahrokhi y col. (1995) .
- ^ Mäkinen (1988) ; Doğrusöz, Madden y Madden (1997) ; Six y Tollis (1999a) ; Él y Sýkora (2004) ; Baur y Brandes (2005) .
- ^ Verbitsky (2008) .
- ^ Mäkinen (1988) ; Gansner y Koren (2007) ; Nguyen y col. (2011) ; Dehkordi y col. (2013) .
- ^ Mäkinen (1988) .
Referencias
- Baur, Michael; Brandes, Ulrik (2005), "Crossing reducción en diseños circulares", en van Leeuwen, Jan (ed.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Alemania, 21-23 de junio, 2004, Revised Papers , Lecture Notes in Computer Science , 3353 , Springer, págs. 332–343, doi : 10.1007 / 978-3-540-30559-0_28.
- Becker, Moritz Y .; Rojas, Isabel (2001), "Un algoritmo de diseño de gráficos para dibujar vías metabólicas", Bioinformatics , 17 (5): 461–467, doi : 10.1093 / bioinformatics / 17.5.461 , PMID 11331241.
- Dehkordi, Hooman Reisi; Nguyen, Quan; Eades, Peter ; Hong, Seok-Hee (2013), "Dibujos de gráficos circulares con grandes ángulos de cruce", Algoritmos y cómputo: 7mo Taller Internacional, WALCOM 2013, Kharagpur, India, 14-16 de febrero de 2013, Actas , Lecture Notes in Computer Science, 7748 , Springer, págs. 298-309, doi : 10.1007 / 978-3-642-36065-7_28.
- Doğrusöz, Uğur; Belviranli, M .; Dilek, A. (2012), "CiSE: Un algoritmo de diseño de embebedor de resorte circular", IEEE Transactions on Visualization and Computer Graphics , 19 (6): 953–966, doi : 10.1109 / TVCG.2012.178 , hdl : 11693/21006 , PMID 23559509 , S2CID 14365664.
- Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), "Diseño circular en el conjunto de herramientas de diseño de gráficos", Dibujo de gráficos: Simposio sobre dibujo de gráficos, GD '96, Berkeley, California, EE. UU., 18-20 de septiembre de 1996, Actas , Lecture Notes in Computer Science, 1190 , Springer, págs. 92–100, doi : 10.1007 / 3-540-62495-3_40.
- Duncan, Christian A .; Eppstein, David ; Goodrich, Michael T .; Kobourov, Stephen G .; Nöllenburg, Martin (2012), "Lombardi drawings of graphs", Journal of Graph Algorithms and Applications , 16 (1): 85–108, arXiv : 1009.0579 , doi : 10.7155 / jgaa.00251.
- Gansner, Emden R .; Koren, Yehuda (2007), Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Alemania, 18-20 de septiembre de 2006, Revised Papers , Lecture Notes in Computer Science, 4372 , Springer, págs. 386–398, doi : 10.1007 / 978-3-540-70904-6_37.
- Él, H .; Sýkora, Ondrej (2004), "Nuevos algoritmos de dibujo circular", Actas del Taller sobre tecnologías de la información: aplicaciones y teoría (ITAT), Eslovaquia, 15-19 de septiembre.
- Huang, Weidong; Hong, Seok-Hee; Eades, Peter (2007), "Efectos de las convenciones de dibujo de sociogramas y cruces de bordes en la visualización de redes sociales", Journal of Graph Algorithms and Applications , 11 (2): 397–429, doi : 10.7155 / jgaa.00152.
- Iragne, Florian; Nikolski, Macha; Mathieu, Bertrand; Auber, David; Sherman, David (2005), "ProViz: visualización y exploración de interacciones de proteínas", Bioinformatics , 21 (2): 272–274, doi : 10.1093 / bioinformatics / bth494 , PMID 15347570.
- Krebs, Valdis (1996), "Visualizando redes humanas" (PDF) , Versión 1.0: Informe mensual de Esther Dyson , 2-96.
- Mäkinen, Erkki (1988), "On circular layouts", International Journal of Computer Mathematics , 24 (1): 29–37, doi : 10.1080 / 00207168808803629.
- Masuda, S .; Kashiwabara, T .; Nakajima, K .; Fujisawa, T. (1987), "On the NP-completeness of a computer network layout problem", Proceedings of the IEEE International Symposium on Circuits and Systems , págs. 292-295. Según lo citado por Baur & Brandes (2005) .
- Nguyen, Quan; Eades, Peter ; Hong, Seok-Hee; Huang, Weidong (2011), "Grandes ángulos de cruce en diseños circulares", Dibujo gráfico: 18º Simposio Internacional, GD 2010, Konstanz, Alemania, 21-24 de septiembre de 2010, Artículos seleccionados revisados , Lecture Notes in Computer Science, 6502 , Springer , págs. 397–399, doi : 10.1007 / 978-3-642-18469-7_40.
- Pisanski, Tomaž ; Servatius, Brigitte (2013), "2.3.2 Gráficos cúbicos y notación LCF", Configuraciones desde un punto de vista gráfico , Springer, p. 32, ISBN 9780817683641.
- Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A .; Vrt'o, Imrich (1995), "Incrustaciones de libros y números cruzados", Conceptos teóricos de gráficos en ciencias de la computación: 20º Taller internacional, WG '94, Herrsching, Alemania, 16-18 de junio de 1994, Actas , Notas de conferencias en computadora Science, 903 , Springer, págs. 256–268, doi : 10.1007 / 3-540-59071-4_53.
- Six, Janet M .; Tollis, Ioannis G. (1999a), "Dibujos circulares de gráficos biconectados", Ingeniería de algoritmos y experimentación: Taller internacional ALENEX'99, Baltimore, MD, EE. UU., 15-16 de enero de 1999, Documentos seleccionados , Notas de conferencias en Ciencias de la Computación, 1619 , Springer, págs. 57–73, doi : 10.1007 / 3-540-48518-X_4.
- Six, Janet M .; Tollis, Ioannis G. (1999b), "Un marco para dibujos circulares de redes", Dibujo gráfico: 7º Simposio Internacional, GD'99, Castillo de Štiřín, República Checa, 15-19 de septiembre de 1999, Actas , Notas de conferencias en Ciencias de la Computación , 1731 , Springer, págs. 107-116, doi : 10.1007 / 3-540-46648-7_11.
- Symeonidis, Alkiviadis; Tollis, Ioannis G. (2004), "Visualización de información biológica con dibujos circulares", Análisis de datos biológicos y médicos: 5to Simposio Internacional, ISBMDA 2004, Barcelona, España, 18-19 de noviembre de 2004, Actas , Notas de conferencia en Ciencias de la Computación , 3337 , Springer, págs. 468–478, doi : 10.1007 / 978-3-540-30547-7_47.
- Verbitsky, Oleg (2008), "Sobre la complejidad de la ofuscación de los gráficos planos", Informática teórica , 396 (1-3): 294-300, arXiv : 0705.3748 , doi : 10.1016 / j.tcs.2008.02.032 , MR 2412266 , S2CID 5948167.