Un diagrama de arco es un estilo de dibujo de gráficos , en el que los vértices de un gráfico se colocan a lo largo de una línea en el plano euclidiano , con bordes dibujados como semicírculos en uno o ambos de los dos semiplanos delimitados por la línea, o como curvas suaves formadas por secuencias de semicírculos. En algunos casos, los segmentos de línea de la propia línea también se permiten como bordes, siempre que conecten solo vértices que sean consecutivos a lo largo de la línea. Las variaciones de este estilo de dibujo en las que los semicírculos se reemplazan por curvas convexas de algún otro tipo también se denominan comúnmente diagramas de arco. [1]
El uso de la frase "diagrama de arco" para este tipo de dibujo sigue el uso de un tipo similar de diagrama por Wattenberg (2002) para visualizar los patrones de repetición en cadenas, utilizando arcos para conectar pares de subcadenas iguales. Sin embargo, este estilo de dibujo de grafos es mucho más antiguo que su nombre, remontándose al trabajo de Saaty (1964) y Nicholson (1968), quienes utilizaron diagramas de arco para estudiar números cruzados de grafos . Un nombre más antiguo pero menos utilizado para los diagramas de arco es incrustaciones lineales . [2] Más recientemente, los diagramas de arco se han utilizado en el marco de la topología de circuitos de nudos y enredos, donde se denominan diagramas de circuitos . [3]
Heer, Bostock y Ogievetsky (2010) escriben que los diagramas de arco "pueden no transmitir la estructura general del gráfico de manera tan efectiva como un diseño bidimensional", pero que su diseño facilita la visualización de datos multivariados asociados con los vértices del gráfico. Las aplicaciones de los diagramas de arco incluyen el diagrama de Farey , una visualización de conexiones de teoría de números entre números racionales , y diagramas que representan la estructura secundaria del ARN en los que los cruces del diagrama representan pseudonudos en la estructura.
Como observó Nicholson (1968), cada dibujo de un grafo en el plano puede deformarse para formar un diagrama de arcos, sin cambiar su número de cruces. En particular, cada grafo plano tiene un diagrama de arcos plano. Sin embargo, esta incrustación puede necesitar utilizar más de un semicírculo para algunas de sus aristas.
Si se dibuja un grafo sin cruces utilizando un diagrama de arco en el que cada arista es un semicírculo único, entonces el dibujo es una incrustación de libro de dos páginas , algo que solo es posible para los grafos subhamiltonianos , un subconjunto propio de los grafos planares. [4] Por ejemplo, un grafo planar maximal tiene tal incrustación si y solo si contiene un ciclo hamiltoniano . Por lo tanto, un grafo planar maximal no hamiltoniano como el grafo de Goldner-Harary no puede tener una incrustación plana con un semicírculo por arista. Probar si un grafo dado tiene un diagrama de arco sin cruces de este tipo (o equivalentemente, si tiene la página número dos) es NP-completo . [5]
Sin embargo, cada grafo plano tiene un diagrama de arco en el que cada arista se dibuja como un biarco con a lo sumo dos semicírculos. Más fuertemente, cada grafo dirigido st -planar (un grafo acíclico dirigido planar con una sola fuente y un solo sumidero, ambos en la cara exterior) tiene un diagrama de arco en el que cada arista forma una curva monótona, con estas curvas todas orientadas consistentemente desde un extremo de la línea de vértice hacia el otro. [6] Para grafos planos no dirigidos, una forma de construir un diagrama de arco con a lo sumo dos semicírculos por arista es subdividir el grafo y agregar aristas adicionales para que el grafo resultante tenga un ciclo hamiltoniano (y de modo que cada arista se subdivida a lo sumo una vez), y usar el orden de los vértices en el ciclo hamiltoniano como el orden a lo largo de la línea. [7] En un grafo plano con vértices, se necesitan a lo sumo biarcos. [8]
Debido a que es NP-completo probar si un gráfico dado tiene un diagrama de arco con un semicírculo por arista y sin cruces, también es NP-difícil encontrar un diagrama de arco de este tipo que minimice el número de cruces. Este problema de minimización de cruces sigue siendo NP-difícil, para gráficos no planos, incluso si el orden de los vértices a lo largo de la línea es fijo. [2] Sin embargo, en el caso de orden fijo, una incrustación sin cruces (si existe una) se puede encontrar en tiempo polinomial traduciendo el problema en un problema de 2-satisfacibilidad , en el que las variables representan la ubicación de cada arco y las restricciones evitan que los arcos que se cruzan se coloquen en el mismo lado de la línea de vértices. [9] Además, en el caso de orden fijo, una incrustación que minimiza los cruces se puede aproximar resolviendo un problema de corte máximo en un gráfico auxiliar que representa los semicírculos y sus cruces potenciales (o equivalentemente, aproximando la versión MAX2SAT de la instancia de 2-satisfacibilidad). [10]
Cimikowski y Shope (1996), Cimikowski (2002) y He, Sýkora y Vrt'o (2005) analizan heurísticas para encontrar diagramas de arco con pocos cruces.
Para los dibujos de grafos dirigidos , una convención común es dibujar cada arco en el sentido de las agujas del reloj, de modo que los arcos que se dirigen desde un vértice anterior a uno posterior en la secuencia se dibujen por encima de la línea del vértice, y los arcos dirigidos desde un vértice posterior a uno anterior se dibujen por debajo de la línea. Esta convención de orientación en el sentido de las agujas del reloj fue desarrollada como parte de un estilo de dibujo de grafos diferente por Fekete et al. (2003), y aplicada a los diagramas de arcos por Pretorius y van Wijk (2007).
El diagrama de Farey de un conjunto de números racionales es una estructura que puede representarse geométricamente como un diagrama de arco. En esta forma tiene un vértice para cada número, colocado en la línea numérica , y un borde semicircular sobre la línea que conecta pares de números y (en términos más simples) para los cuales . Los semicírculos del diagrama pueden considerarse como líneas en el modelo de semiplano de Poincaré del plano hiperbólico , con los vértices colocados en puntos infinitos en la línea límite de este modelo. El modelo de semiplano de Poincaré tiene un punto infinito que no se representa como punto en la línea límite, el punto final compartido de todos los rayos verticales en el modelo, y esto puede representarse por la "fracción" 1/0 (no definida como un número), con la misma regla para determinar sus adyacencias. El diagrama de Farey de cualquier conjunto de números racionales es un grafo planar, y el diagrama de Farey del conjunto de todos los números racionales forma una teselación del plano hiperbólico por triángulos ideales . [11]
Los diagramas de arco o diagramas de circuito se utilizan comúnmente para estudiar biopolímeros plegados, como proteínas y ácidos nucleicos (ADN, ARN). Los biopolímeros se representan típicamente por su secuencia monomérica primaria a lo largo de la línea de los diagramas, y con arcos sobre la línea que representan enlaces entre monómeros (por ejemplo, aminoácidos en proteínas o bases en ARN o ADN) que son adyacentes en la estructura física del polímero a pesar de no ser adyacentes en el orden de secuencia. El marco teórico de la topología de circuito se aplica típicamente para extraer información topológica local y global, que a su vez puede estar relacionada con la función biológica de las moléculas plegadas. [12] Cuando los arcos no se cruzan, la disposición de los dos arcos será paralela (P) o en serie (S). Cuando hay cruces, los cruces representan lo que a menudo se denomina disposición X en topología de circuito. Las estadísticas de P, S y X se pueden utilizar para aprender sobre la cinética de plegamiento de estos polímeros. [13]
Los diagramas de arco fueron utilizados por Brandes (1999) para visualizar el diagrama de estado de un registro de desplazamiento , por Djidjev y Vrt'o (2002) para mostrar que el número de cruces de cada gráfico está limitado inferiormente por una combinación de su ancho de corte y grados de vértice, por Byrne et al. (2007) para visualizar interacciones entre dispositivos Bluetooth , y por Owens y Jankun-Kelly (2013) para visualizar las yardas de las jugadas en un partido de fútbol americano . Nagel y Duval (2013) examinan aplicaciones adicionales de esta técnica de visualización.
