Arreglo circular

La disposición circular es un  estilo de visualización de gráficos en el que los vértices de un gráfico se organizan en un círculo , a menudo espaciados uniformemente, de modo que forman los vértices de un polígono regular .

Aplicación

La disposición circular es adecuada para topologías de comunicación de red como estrella o anillo [1] , así como para partes cíclicas de redes metabólicas [2] . Para gráficos con un ciclo hamiltoniano conocido, la disposición circular permite representar el ciclo como un círculo; tal arreglo circular forma la base para el código LCF de grafos cúbicos hamiltonianos [3] .

La disposición circular se puede usar para visualizar un gráfico completo, pero también se puede usar para fragmentos como grupos de vértices de gráficos, sus componentes doblemente conectados [1] [4] , grupos de genes en un gráfico de interacción de genes [5] o subgrupos naturales en una red social [6] . Usando círculos múltiples con vértices de gráficos, se pueden aplicar otros métodos de agrupamiento, como algoritmos de visualización de fuerza [7] .

La ventaja de un arreglo circular en campos como la bioinformática o la visualización de redes sociales radica en su neutralidad visual [8]  - cuando todos los vértices están ubicados a la misma distancia entre sí y del centro de la imagen, ninguno de los nodos ocupa una posición centralizada privilegiada. Esto es importante porque existe una tendencia psicológica a percibir los nodos cercanos al centro como más importantes [9] .

Estilo de borde

Los bordes en una imagen gráfica pueden ser cuerdas circulares [10] , arcos circulares [11] (posiblemente perpendiculares al círculo en un punto, de modo que los bordes del modelo estén dispuestos como líneas rectas en el modelo de geometría hiperbólica de Poincaré ) o otros tipos de curvas [12] .

La distinción visual entre el interior y el exterior de un círculo en una disposición circular se puede utilizar para separar los dos tipos de imágenes de borde. Por ejemplo, el algoritmo de dibujo de círculos de Gansner y Coren [12] utiliza una agrupación de bordes dentro del círculo junto con algunos bordes no agrupados fuera del círculo [12] .

Para una disposición circular de gráficos regulares con bordes dibujados dentro y fuera del círculo como arcos , los ángulos de incidencia (el ángulo con la tangente en un punto) en ambos lados del arco son los mismos, lo que simplifica la optimización de la resolución angular de la figura [11] .

Número de cruces

Algunos autores están estudiando el problema de encontrar una permutación de los vértices de un arreglo circular que minimice el número de intersecciones cuando todos los bordes se dibujan dentro del círculo. Este número de intersección es cero solo para gráficos planos exteriores [10] [13] . Para otros gráficos, se puede optimizar o reducir por separado para cada componente del gráfico biconectado antes de generar una solución, ya que dichos componentes se pueden dibujar sin interactuar entre sí [13] .

En general, minimizar el número de intersecciones es un problema NP-completo [14] , pero se puede aproximar por un factor , donde n es igual al número de vértices [15] . También se han desarrollado métodos heurísticos para reducir la complejidad, como los basados ​​en un orden de inserción de vértices bien pensado y en la optimización local [16] [1] [10] [17] [13] .

También se puede utilizar una disposición circular para maximizar el número de intersecciones. En particular, elegir una permutación aleatoria de los vértices da como resultado una intersección con una probabilidad de 1/3, por lo que el número esperado de intersecciones puede ser tres veces el número máximo de intersecciones entre todas las posibles ubicaciones de vértices. La desaleatorización de este método da un algoritmo de aproximación determinista con un coeficiente de aproximación igual a tres [18] .

Otros criterios de optimalidad

Asimismo, los problemas de disposición circular incluyen la optimización de la longitud de las aristas de la disposición circular, la resolución angular de las intersecciones o el ancho del corte (el número máximo de aristas que conectan los arcos circulares con los opuestos) [16] [12] [19] [20] ; muchos de estos problemas son NP-completos [16] .

Véase también

Notas

  1. ↑ 1 2 3 Dogrusöz, Madden, Madden, 1997 .
  2. ↑ Becker, Rojas, 2001 .
  3. ↑ Pisanski, Servatius, 2013 .
  4. ↑ Seis, Tollis, 1999b .
  5. ↑ Symeonidis, Tollis, 2004 .
  6. ↑ Krebs, 1996 .
  7. ↑ Doğrusöz, Belviranli, Dilek, 2012 .
  8. ↑ Iragne, Nikolski, Mathieu, Auber, Sherman, 2005 .
  9. ↑ Huang, Hong, Eades, 2007 .
  10. ↑ 1 2 3 Seis, Tollis, 1999a .
  11. ↑ 1 2 Duncan, Eppstein, Goodrich, Kobourov, Nöllenburg, 2012 .
  12. ↑ 1 2 3 4 Gansner, Koren, 2007 .
  13. ↑ 1 2 3 Baur, Brandes, 2005 .
  14. ↑ Masuda, Kashiwabara, Nakajima, Fujisawa, 1987 .
  15. ↑ Shahrokhi, Sýkora, Székely, Vrt'o, 1995 .
  16. ↑ 1 2 3 Makinen, 1988 .
  17. ↑ Él, Sýkora, 2004 .
  18. ↑ Verbitsky, 2008 .
  19. ↑ Nguyen, Eades, Hong, Huang, 2011 .
  20. ↑ Dehkordi, Nguyen, Eades, Hong, 2013 .

Literatura