Número de pendientes del gráfico

En visualización de gráficos y teoría de gráficos geométricos , el número de pendientes de un gráfico es el número mínimo posible de diferentes coeficientes de pendiente de los bordes en un dibujo de un gráfico en el que los vértices están representados por puntos del plano euclidiano y los bordes son segmentos que no pasan por vértices que no son incidentes con estas aristas.

Gráficos completos

Aunque antes se han estudiado problemas relacionados con la geometría combinatoria (Scott en 1970 y Jamison en 1984), el problema de determinar el número de pendientes de un gráfico fue planteado por Wade y Chu [1] , mostrando que el número de pendientes de un gráfico con n vértices de un grafo completo K n es exactamente n . Se puede obtener un dibujo de un gráfico con tal número de pendientes colocando los vértices del gráfico en las esquinas de un polígono regular .

Relación con el grado de la gráfica

Está claro que el número de pendientes de un grafo de máximo grado d es al menos , ya que como máximo dos aristas incidentes de un vértice de grado d pueden estar en la misma recta (tener una sola pendiente). Más precisamente, el número de pendientes no es inferior a la arborescencia lineal del gráfico , ya que los bordes de una misma pendiente deben formar un bosque lineal, y la arborescencia lineal, a su vez, no debe ser inferior a .

Hay gráficos con un grado máximo de cinco que tienen un número arbitrariamente grande de pendientes [2] . Sin embargo, cualquier gráfico con grado máximo tres tiene como máximo cuatro pendientes [3] . El resultado de Wade y Chu (1994 ) para el gráfico completo K 4 muestra que este límite es agudo. No cualquier conjunto de cuatro pendientes es adecuado para dibujar todas las gráficas de grado 3; un conjunto de pendientes es adecuado para dibujar si y sólo si son las pendientes de los lados y las diagonales del paralelogramo . En particular, cualquier gráfico de grado 3 se puede dibujar de modo que sus bordes sean paralelos a los ejes o paralelos a las diagonales principales de la red de enteros [4] . Se desconoce si el número de pendientes de los gráficos con un grado máximo de cuatro está acotado o no [5] .

Grafos planos

Como han demostrado Keszegh, Pach, Pálvölgyi (2011 ), cualquier gráfico plano tiene un patrón de segmento de línea plano en el que el número de pendientes diferentes es una función del grado del gráfico. Su demostración sigue la construcción de Malitz y Papakostas ( Malitz, Papakostas (1994 )) para limitar la resolución angular de los gráficos planos en función del grado. La restricción de grados se realiza aumentando el gráfico a un gráfico plano máximo sin aumentar su grado en más de un factor constante y luego aplicando el teorema de empaquetamiento de círculos para representar este gráfico extendido como un conjunto de círculos tangentes. Si el grado del gráfico inicial está acotado, la relación de los radios de los círculos adyacentes en el empaque también estará acotada [7] , lo que a su vez implica que la aplicación de un quadtree a todos los vértices del gráfico en un punto dentro del círculo da pendientes que son razones de números enteros pequeños. El número de pendientes diferentes obtenidas en esta construcción es un exponente del grado de la gráfica.

Dificultad

El problema de determinar si el número de pendientes es igual a dos es NP-completo [8] [9] [10] . Esto implica que es un problema NP-difícil determinar el número de pendientes de un gráfico arbitrario o aproximar este número con una eficiencia garantizada mejor que 3/2.

Si un gráfico plano es un dibujo plano con dos pendientes también es un problema NP-completo [11] .

Notas

  1. ↑ Wade, Chu, 1994 .
  2. ↑ Demostrado de forma independiente por Barat, Matoušek, Wood (2006 ) y Pach, Pálvölgyi (2006 ) cuando resolvieron el problema planteado por Dujmovic, Suderman y Sharir ( Dujmović, Suderman, Wood (2005) ). Véanse los teoremas 5.1 y 5.2 en Pach y Sharir ( Pach y Sharir (2009 )).
  3. ↑ Mukkamala , Szegedy (2009 ), quien mejoró el resultado anterior de Keszegh, Pálvölgyi, Tóth (2008 )). Consulte el Teorema 5.3 de Pach y Sharir ( Pach y Sharir (2009 )).
  4. ↑ Mukkamala, Pálvölgyi, 2012 .
  5. ↑ Pach, Sharir, 2009 .
  6. ↑ Keszegh, Pach, Pálvölgyi, 2011 .
  7. ↑ Hansen, 1988 .
  8. ↑ Formann, Hagerup, Haralambides, Kaufmann, 1993 .
  9. ↑ Eades, Hong, Poon, 2010 .
  10. ↑ Mañuch, Patterson, Poon, Thachuk, 2011 .
  11. ↑ Garg, Tamassia, 2001 .

Literatura