Diagrama de arco
Un diagrama de arco es un estilo de dibujo de gráfico , en el que los vértices de un gráfico se colocan a lo largo de una línea en el plano euclidiano , con los bordes dibujados como semicírculos en uno o ambos de los dos medios planos delimitados por la línea, o como curvas suaves. formado por secuencias de semicírculos. En algunos casos, los segmentos de línea de la línea en sí también se permiten como bordes, siempre que conecten solo los vértices que son consecutivos a lo largo de la línea. Las variaciones de este estilo de dibujo en el 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 de 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 gráficos es mucho más antiguo que su nombre, y se remonta al trabajo de Saaty (1964) y Nicholson (1968) , quienes utilizaron diagramas de arco para estudiar los números cruzados de gráficos . Un nombre más antiguo pero que se usa con menos frecuencia para los diagramas de arco es incrustaciones lineales . [2]
Heer, Bostock y Ogievetsky (2010) escriben que los diagramas de arco "pueden no transmitir la estructura general del gráfico con tanta eficacia 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 teóricas 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 gráfico en el plano puede deformarse en un diagrama de arco, sin cambiar su número de cruces. En particular, cada gráfico plano tiene un diagrama de arco plano. Sin embargo, esta incrustación puede necesitar usar más de un semicírculo para algunos de sus bordes.
Si se dibuja un gráfico sin cruces usando un diagrama de arco en el que cada borde es un solo semicírculo, entonces el dibujo es un libro de dos páginas incrustado , algo que solo es posible para los gráficos subhamiltonianos , un subconjunto adecuado de los gráficos planos. [3] Por ejemplo, un gráfico plano máximo tiene tal incrustación si y solo si contiene un ciclo hamiltoniano . Por lo tanto, un gráfico plano máximo no hamiltoniano como el gráfico de Goldner-Harary no puede tener una incrustación plana con un semicírculo por borde. Probar si un gráfico dado tiene un diagrama de arco sin cruce de este tipo (o, de manera equivalente, si tiene un número de página dos) es NP-completo . [4]
Sin embargo, cada gráfico plano tiene un diagrama de arco en el que cada borde se dibuja como un biarco con un máximo de dos semicírculos. Más fuertemente, cada grafo dirigido en st -planar (un grafo acíclico dirigido en plano con una sola fuente y un solo sumidero, ambos en la cara exterior) tiene un diagrama de arco en el que cada borde forma una curva monótona, con estas curvas todas consistentemente orientadas desde un extremo de la línea del vértice hacia el otro. [5] Para gráficos planos no dirigidos, una forma de construir un diagrama de arco con un máximo de dos semicírculos por borde es subdividir el gráfico y agregar bordes adicionales para que el gráfico resultante tenga un ciclo hamiltoniano.(y para que cada borde se subdivida como máximo una vez), y utilizar el orden de los vértices en el ciclo hamiltoniano como el orden a lo largo de la línea. [6] En un gráfico plano con vértices, se necesitan como máximo biarcs. [7]
