stringtranslate.com

Disposición circular

Disposición circular del grafo de Chvátal
Disposición circular de un diagrama de estados para el protocolo de puerta de enlace fronteriza
Construcción incremental de un diseño circular para el modelo Barabási-Albert de formación de redes sociales

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 son una buena opción para topologías de redes de comunicaciones como redes en estrella o en anillo , [1] y para las partes cíclicas de redes metabólicas . [2] Para gráficos con un ciclo hamiltoniano conocido , un diseño circular permite representar el ciclo como un 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 dibujar un gráfico completo, pero también puede usarse como diseño para grupos más pequeños de vértices dentro de un gráfico más grande, como sus componentes biconectados , [4] grupos de genes en un gráfico de interacción genética, [5] o subgrupos naturales dentro de una red social . [6] Si se usan múltiples círculos de vértices de esta manera, se pueden usar otros métodos como el dibujo de gráficos dirigido por 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 del centro del dibujo, ninguno obtiene una posición privilegiada, 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 líneas del modelo de disco de Poincaré de geometría hiperbólica ), o como otros tipos de curva. [12]

La distinción visual entre el interior y el exterior del círculo de vértices en un diseño circular se puede utilizar para separar dos estilos diferentes de dibujo de aristas. Por ejemplo, un algoritmo de dibujo circular de Gansner y Koren (2007) utiliza la agrupación de aristas dentro del círculo, junto con algunas aristas que no están agrupadas, dibujadas fuera del círculo. [12]

Para diseños circulares de gráficos regulares , con aristas dibujadas tanto internas como externas 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 de la resolución angular del dibujo. [11]

Número de cruces

Varios autores han estudiado el problema de encontrar una permutación de los vértices de un trazado 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 grafos planos exteriores . [13] Para otros grafos, se puede optimizar o reducir por separado para cada componente biconectado del grafo antes de combinar las soluciones, ya que estos componentes se pueden dibujar de modo que no interactúen. [14] En general, minimizar el número de cruces es NP-completo . [15]

Shahrokhi et al. (1995) describieron un algoritmo de aproximación basado en cortes equilibrados o separadores de aristas, subconjuntos de pocas aristas cuya eliminación desconecta el grafo dado en dos subgrafos con números aproximadamente iguales de vértices. Después de encontrar un corte aproximado, su algoritmo organiza los dos subgrafos en cada lado del corte recursivamente, sin considerar los cruces adicionales formados por las aristas que cruzan el corte. Demuestran que el número de cruces que ocurren en el diseño resultante, en un grafo con vértices, es donde es el número óptimo de cruces y es la razón de aproximación del algoritmo de corte equilibrado utilizado por este método de diseño. [16] Su trabajo cita un artículo de Fan Chung y Shing-Tung Yau de 1994 que afirmaba , pero luego se descubrió que tenía una prueba errónea. [17] En cambio, la mejor aproximación conocida para el problema de corte equilibrado es , [18] lo que le da a este algoritmo de diseño circular una relación de aproximación de en gráficos que tienen una gran cantidad de cruces en relación con sus grados de vértice .

También se han ideado métodos heurísticos para reducir la complejidad de los cruces, basados, por ejemplo, en un cuidadoso orden de inserción de vértices y en la optimización local . [19] 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 cruce posible 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 desaleatorización de este método proporciona un algoritmo de aproximación determinista con una razón de aproximación de tres. [20]

Otros criterios de optimización

Junto con los cruces, también se han considerado 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), [21] pero muchos de estos problemas son NP-completos. [22]

Véase también

Enlaces externos

Notas

  1. ^ Doğrusöz, Madden y Madden (1997).
  2. ^ Becker y Rojas (2001).
  3. ^ Pisanski y Servacio (2013).
  4. ^ Doğrusöz, Madden y Madden (1997); Seis y Tollis (1999b).
  5. ^ Symeonidis y Tollis (2004).
  6. ^ Cáncer (1996).
  7. ^ Doğrusöz, Belviranli y Dilek (2012).
  8. ^ Iragne y otros (2005).
  9. ^ Huang, Hong y Eades (2007).
  10. ^ Seis y Tollis (1999a).
  11. ^ desde Duncan y col. (2012).
  12. ^ por Gansner y Koren (2007).
  13. ^ Seis y Tollis (1999a); Baur y Brandes (2005).
  14. ^ Baur y Brandes (2005).
  15. ^ Masuda y otros (1987).
  16. ^ Shahrokhi y otros (1995).
  17. ^ Shmoys (1997).
  18. ^ Arora, Rao y Vazirani (2009).
  19. ^ Makinen (1988); Doğrusöz, Madden y Madden (1997); Seis y Tollis (1999a); Él y Sýkora (2004); Baur y Brandes (2005).
  20. ^ Verbitsky (2008).
  21. ^ Makinen (1988); Gansner y Koren (2007); Nguyen et al. (2011); Dehkordi et al. (2013).
  22. ^ Mäkinen (1988).

Referencias