Resolución angular (teoría de grafos)

La resolución angular de un dibujo gráfico se refiere al ángulo más agudo formado por dos aristas que se encuentran en el mismo vértice en el dibujo.

Propiedades

Relación con el grado del vértice

Foreman y otros [1] observaron que cualquier dibujo de un gráfico con aristas de segmento con grado máximo d tiene una resolución angular que no excede — si v es un vértice con grado d , entonces las aristas incidentes en v dividen el espacio alrededor del vértice v en d cuñas con ángulo total , y la menor de estas cuñas debe tener un ángulo que no exceda de . Más estrictamente, si el gráfico es d - regular , debe tener una resolución angular menor que , ya que esta es la mejor resolución que se puede obtener para un vértice en el casco convexo de la figura.

Relación con la coloración del gráfico

Como muestran Foreman et al .[1] , la mayor resolución angular posible de un grafo G está íntimamente relacionada con el número cromático del cuadrado del grafo G 2 , es decir, un grafo con el mismo conjunto de vértices en el que cada par de vértices está conectado por una arista si la distancia entre ellos en el gráfico G no es superior a dos. Si el gráfico G 2 se puede colorear con colores, entonces G se puede dibujar con resolución angular para cualquier , asignando diferentes colores a los vértices de un -gon regular y colocando cada vértice de G junto a un vértice de polígono con el mismo color. Usando esta construcción, demostraron que cualquier gráfico con grado máximo d tiene un patrón con una resolución angular proporcional a 1/ d 2 . Este límite es casi exacto: usaron un método probabilístico para probar la existencia de gráficos con un grado máximo de d , todos cuyos dibujos tienen resolución angular .

Existencia de patrones óptimos

Forman et al [1] dieron un ejemplo que muestra que hay gráficos que no tienen patrones con la máxima resolución angular posible. Por el contrario, estos gráficos tienen una familia de dibujos cuyas resoluciones angulares tienden a algún valor limitado, pero no lo alcanzan. Específicamente, presentaron un gráfico de 11 vértices que tiene un patrón con una resolución angular de cualquier , pero no tiene un patrón con una resolución angular de exactamente .

Clases especiales de grafos

Arboles

Cualquier árbol se puede dibujar de tal manera que los bordes se distribuyan uniformemente alrededor de cada vértice, una propiedad conocida como resolución angular perfecta . Además, si los bordes se pueden permutar libremente alrededor de cada vértice, entonces dicho patrón es posible sin intersecciones con bordes de longitud uno o más, y el patrón completo se coloca en un rectángulo de área polinomial . Sin embargo, si el orden circular de las aristas alrededor de cada vértice ya se especifica como parte del enunciado del problema, entonces obtener una resolución angular sin cruces a veces puede requerir un área exponencial [2] [3] .

Gráficos exteriores

La resolución angular perfecta no siempre es posible para gráficos planos exteriores , ya que los vértices en el casco convexo de un patrón con un grado mayor que uno no pueden tener bordes incidentes distribuidos uniformemente alrededor del vértice. Sin embargo, cualquier gráfico de plano exterior con un grado máximo d tiene un dibujo de plano exterior con una resolución angular proporcional a 1/ d [4] [5] .

Grafos planos

Para gráficos planos con grado máximo d , la técnica de coloreado de cuadrados de gráficos de Foreman (et al.) [1] produce un dibujo con una resolución angular proporcional a 1/ d , ya que el cuadrado de un gráfico plano debe tener un número cromático proporcional a d . Wegner conjeturó en 1977 que el número cromático del cuadrado de un grafo plano no excede y se sabe que el número cromático no excede [6] [7] . Sin embargo, el patrón obtenido por esta técnica generalmente no es plano.

Para algunos gráficos planos, la resolución angular óptima de un dibujo plano con segmentos de línea es O(1/ d 3 ) , donde d es el grado del gráfico [5] . Además, tales patrones pueden verse obligados a tener bordes muy largos, más largos que el factor exponencial del borde más corto del patrón. Malitz y Papakostas [4] utilizaron el teorema de empaquetamiento de círculos para mostrar que cualquier gráfico plano con grado máximo d tiene un patrón plano cuya resolución angular en el peor de los casos es una función exponencial de d e independiente del número de vértices del gráfico.

Complejidad computacional

El problema de determinar si un gráfico dado con grado máximo d tiene un patrón con resolución angular es NP-difícil incluso en el caso especial d =4 [1] [8] . Sin embargo, para algunas clases limitadas de dibujos, incluidos los dibujos de árboles, en los que la extensión de las hojas hasta el infinito da una partición convexa del plano, así como dibujos de gráficos planos, en los que cada cara delimitada es un polígono centralmente simétrico, un el dibujo con resolución angular óptima se puede encontrar en tiempo polinomial [9] [10] .

Historia

La resolución angular fue determinada por Forman et al .[1] .

Aunque originalmente se definió para dibujos de gráficas con aristas rectas, autores posteriores investigaron la resolución angular de dibujos en los que las aristas son poligonales [11] [12] , arcos circulares [13] [2] o splines [14] [15] .

La resolución angular de un gráfico está estrechamente relacionada con la resolución de su intersección, los ángulos formados por las intersecciones en el dibujo del gráfico. En particular, dibujar gráficos en ángulos rectos busca una representación que asegure que todos esos ángulos son ángulos rectos , que es el ángulo de intersección más grande posible [16]

Notas

  1. ↑ 1 2 3 4 5 6 Formann, Hagerup, Haralambides et al., 1993 .
  2. ↑ 1 2 Duncan, Eppstein, Goodrich et al., 2011 .
  3. ↑ Halupczok, Schulz, 2011 .
  4. ↑ 1 2 Malitz, Papakostas, 1994 .
  5. ↑ 1 2 Garg, Tamassia, 1994 .
  6. ↑ Kramer, Kramer, 2008 .
  7. ↑ Molloy, Salavatipour, 2005 .
  8. ↑ Garg, Tamassia, 1995 .
  9. ↑ Carlson, Eppstein, 2007 .
  10. ↑ Eppstein, Wortman, 2011 .
  11. ↑ Kant, 1996 .
  12. ↑ Gutwenger, Mutzel, 1998 .
  13. ↑ Cheng, Duncan, Goodrich, Kobourov, 1999 .
  14. ↑ Brandes, Shubina, Tamassia, 2000 .
  15. ↑ Finkel, Tamassia, 2005 .
  16. ↑ Didimo, Eades, Liotta, 2009 .

Literatura