Disposición circular

En el dibujo de gráficos , una disposición circular es un estilo de dibujo que coloca los vértices de un gráfico sobre un círculo , a menudo espaciados uniformemente de manera que formen los vértices de un polígono regular .

Las configuraciones circulares se adaptan bien a topologías de redes de comunicaciones como las redes en estrella o en anillo , ^{[ 1 ]} y a las partes cíclicas de las redes metabólicas . ^{[ 2 ]} Para grafos con un ciclo hamiltoniano conocido , una configuración circular permite representar el ciclo como un círculo, y de esta manera las configuraciones circulares forman la base de la notación LCF para grafos cúbicos hamiltonianos . ^{[ 3 ]}

Un diseño circular puede usarse solo para dibujar un grafo completo, pero también puede usarse como diseño para grupos más pequeños de vértices dentro de un grafo más grande, como sus componentes biconectadas , ^{[ 4 ]} grupos de genes en un grafo de interacción genética, ^{[ 5 ]} o subgrupos naturales dentro de una red social . ^{[ 6 ]} Si se usan varios círculos de vértices de esta manera, se pueden usar otros métodos, como el dibujo de grafos dirigido por fuerzas, 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 recibe una posición privilegiada, contrarrestando la tendencia de los espectadores a percibir los nodos ubicados más al centro como más importantes. ^{[ 9 ]}

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 modelan líneas del modelo de disco de Poincaré de la geometría hiperbólica ), o como otros tipos de curvas. ^{[ 12 ]}

La distinción visual entre el interior y el exterior del círculo del vértice en un diseño circular puede utilizarse 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 y se dibujan fuera del círculo. ^{[ 12 ]}

Para diseños circulares de grafos regulares , con aristas dibujadas 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 de la resolución angular del dibujo. ^{[ 11 ]}

Varios autores han estudiado el problema de encontrar una permutación de los vértices de una disposición 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 exteriores planares . ^{[ 13 ]} Para otros grafos, puede optimizarse o reducirse por separado para cada componente biconexo del grafo antes de combinar las soluciones, ya que estos componentes pueden dibujarse de manera 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 un número aproximadamente igual de vértices. Después de encontrar un corte aproximado, su algoritmo organiza los dos subgrafos a cada lado del corte de forma recursiva, sin considerar los cruces adicionales formados por las aristas que cruzan el corte. Demuestran que el número de cruces que ocurren en la disposición resultante, en un grafo${\displaystyle G}$con${\displaystyle n}$vértices, es $${\displaystyle O{\Bigl (}{\bigl (}\rho \log n{\bigr )}^{2}\cdot {\bigl (}C+\sum _{v\in V(G)}\deg(v)^{2}{\bigr )}{\Bigr )},}$$ dónde${\displaystyle C}$es el número óptimo de cruces y${\displaystyle \rho }$es la relació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${\displaystyle \rho =O(1)}$, pero más tarde se descubrió que tenía una demostración errónea. ^{[ 17 ]} En cambio, la mejor aproximación conocida para el problema del corte equilibrado tiene${\displaystyle \rho =O({\sqrt {\log n}})}$, ^{[ 18 ]} lo que le da a este algoritmo de diseño circular una relación de aproximación de${\displaystyle O(\log ^{3}n)}$en grafos que tienen un gran número de cruces en relación con los grados de sus vértices .

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 . ^{[ 19 ]} También se puede utilizar una disposición circular para maximizar el número de cruces. En particular, elegir 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 todas las disposiciones posibles. Al eliminar la aleatoriedad de este método se obtiene un algoritmo de aproximación determinista con una razón de aproximación de tres. ^{[ 20 ]}

Además de 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 ]}

• Diagrama de cuerdas (visualización de información) , un concepto estrechamente relacionado en la visualización de información.
• Planarity , un rompecabezas en el que un jugador debe mover vértices para desenredar el dibujo de un grafo planar , partiendo de una disposición circular aleatoria.

• Motor de diseño circular de Graphviz