Un diagrama de arco es un estilo de representación gráfica en el que los vértices están dispuestos a lo largo de una línea recta en el plano euclidiano y los bordes se dibujan como semicírculos en uno de los dos semiplanos, o como curvas suaves formadas por los semicírculos. En algunos casos, los segmentos de línea también se usan para representar los bordes del gráfico si conectan vértices adyacentes en la línea.
El nombre "diagrama de arco" para esta representación de gráficos es un sucesor del uso de un tipo similar de diagrama de Wattenberg [1] , que utilizó para visualizar fragmentos repetidos de líneas conectando pares de subcadenas idénticas. Sin embargo, el estilo de representación gráfica en sí es mucho más antiguo que el nombre y data del trabajo de Saaty [2] y Nicholson [3] , quienes utilizaron diagramas de arco para estudiar el número de intersección de las gráficas . Un nombre más antiguo pero menos utilizado para los diagramas de arco es incrustación de líneas [4] .
Heer, Bostock y Ogiwetsky [5] escribieron que los diagramas de arco "no pueden expresar la estructura completa de un gráfico con la misma eficacia que una representación bidimensional", pero facilitan la representación de datos multidimensionales asociados con los vértices del gráfico.
Como señaló Nicholson [3] , cualquier incrustación de un gráfico en un plano se puede convertir en un diagrama de arco sin cambiar el número de intersecciones. En particular, cualquier gráfico plano tiene un diagrama de arco plano. Sin embargo, tal anidamiento puede requerir el uso de más de un semicírculo para dibujar algunos de los bordes del gráfico.
Si un gráfico se dibuja sin cruces de arco como un diagrama de arco en el que cada borde está representado por un solo semicírculo, el dibujo es un libro de dos páginas incrustado , lo que solo es posible para los gráficos sub-Hamiltonianos , un subconjunto de gráficos planos [6 ] . Por ejemplo, un gráfico plano maximal 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-Harari no puede tener una incrustación plana con un semicírculo por borde. Verificar si un gráfico dado tiene un diagrama de arco sin intersecciones de este tipo (o, de manera equivalente, el grosor del libro del gráfico es dos) es un problema NP-completo [7] .
Sin embargo, cualquier gráfico plano tiene un diagrama de arco en el que cada borde se representa como un bi -arco , que consta de dos semicírculos como máximo. Más estrictamente, cualquier gráfico dirigido en st -planar (gráfico acíclico plano dirigido con una fuente y un sumidero, ambos en la cara exterior) tiene un diagrama de arco en el que cualquier borde forma una curva monótona, todas las curvas (bordes) están dirigidos en el mismo dirección [8] . Para gráficos planos no dirigidos, una forma de construir un diagrama de arco con dos semicírculos por arista como máximo es dividir el gráfico y agregar más aristas para obtener un ciclo hamiltoniano (donde las aristas se dividen en dos partes como máximo), luego usar el orden a lo largo del ciclo hamiltoniano como el orden de los vértices en una línea recta [9] .
Dado que verificar si un gráfico dado tiene un diagrama de arco sin intersecciones con un semicírculo por arista es un problema NP-completo, también es un problema NP-difícil encontrar un diagrama de arco que minimice el número de intersecciones. El problema de minimizar el número de intersecciones sigue siendo NP-difícil para gráficos no planos, incluso si ya se da el orden de los vértices a lo largo de la línea [4] . Sin embargo, en el caso de un orden de vértice dado, se puede encontrar una incrustación sin intersección (si existe) en tiempo polinomial convirtiendo el problema en un problema de 2 satisfacibilidad , donde las variables representan la ubicación de cada arco , y las restricciones evitan que dos aristas que se cruzan se ubiquen a lo largo de un lado de la línea con vértices [10] . Además, en el caso de una ubicación fija de vértices, el anidamiento con minimización del número de intersecciones se puede aproximar resolviendo el problema de corte máximo en un gráfico auxiliar que representa semicírculos y sus posibles intersecciones [11] .
Kimikowski, Shoup [12] [13] , He, Sikora y Wrto [14] discutieron algoritmos heurísticos para encontrar diagramas de arco con múltiples intersecciones.
Para representar gráficos dirigidos, la convención general es dirigir los arcos en el sentido de las agujas del reloj, de modo que los arcos de izquierda a derecha se dibujen sobre la línea y los arcos de derecha a izquierda se dibujen debajo de la línea. Esta convención de orientación en el sentido de las agujas del reloj fue desarrollada como parte de otro estilo de representación gráfica por un grupo que incluía a Fekete, Wang, Dang y Aris [15] , y Pretorius y van Wijk [16] aplicaron este estilo a los diagramas de arco .
Los diagramas de arco fueron utilizados por Brandes [17] para visualizar diagramas de estado de registro de desplazamiento , y por Jijev y Wrto [18] para demostrar que el número de intersección de cualquier gráfico es al menos igual al cuadrado de su ancho de corte.