Número de pendiente

En el dibujo de grafos y en la teoría geométrica de grafos , el número de pendiente de un grafo es el número mínimo posible de pendientes distintas de las aristas en un dibujo del grafo en el que los vértices se representan como puntos en el plano euclidiano y las aristas se representan como segmentos de línea que no pasan por ningún vértice no incidente.

Aunque problemas estrechamente relacionados en geometría discreta habían sido estudiados anteriormente, por ejemplo por Scott (1970) y Jamison (1984), el problema de determinar el número de pendiente de un grafo fue introducido por Wade y Chu (1994), quienes demostraron que el número de pendiente de un grafo completo de n vértices K _n es exactamente  n . Un dibujo con este número de pendiente puede formarse colocando los vértices del grafo en un polígono regular .

El número de pendiente de un grafo de grado máximo d es claramente al menos , porque como máximo dos de las aristas incidentes en un vértice de grado d pueden compartir una pendiente. Más precisamente, el número de pendiente es al menos igual a la arboricidad lineal del grafo, ya que las aristas de una sola pendiente deben formar un bosque lineal , y la arboricidad lineal a su vez es al menos . ${\displaystyle \lceil d/2\rceil }$${\displaystyle \lceil d/2\rceil }$

Existen grafos con grado máximo cinco que tienen un número de pendiente arbitrariamente grande. ^[1] Sin embargo, cada grafo de grado máximo tres tiene un número de pendiente como máximo cuatro; ^[2] el resultado de Wade y Chu (1994) para el grafo completo K ₄ muestra que esto es estricto. No todo conjunto de cuatro pendientes es adecuado para dibujar todos los grafos de grado 3: un conjunto de pendientes es adecuado para este propósito si y solo si forma las pendientes de los lados y diagonales de un paralelogramo . En particular, cualquier grafo de grado 3 se puede dibujar de modo que sus bordes sean paralelos al eje o paralelos a las diagonales principales de la red entera . ^[3] No se sabe si los grafos de grado máximo cuatro tienen un número de pendiente acotado o no acotado. ^[4]

Como Keszegh, Pach y Pálvölgyi (2011) demostraron, cada grafo planar tiene un dibujo de línea recta planar en el que el número de pendientes distintas es una función del grado del grafo. Su demostración sigue una construcción de Malitz y Papakostas (1994) para limitar la resolución angular de grafos planares como una función del grado, completando el grafo a un grafo planar máximo sin aumentar su grado en más de un factor constante, y aplicando el teorema de empaquetamiento de círculos para representar este grafo aumentado como una colección de círculos tangentes. Si el grado del grafo inicial está acotado, la relación entre los radios de los círculos adyacentes en el empaquetamiento también estará acotada por el lema del anillo ^[5] , lo que a su vez implica que usar un quadtree para colocar cada vértice del grafo en un punto dentro de su círculo producirá pendientes que son relaciones de números enteros pequeños. El número de pendientes distintas producidas por esta construcción es exponencial en el grado del grafo.

Es NP-completo determinar si un gráfico tiene pendiente número dos. ^[6] De esto se deduce que es NP-difícil determinar el número de pendiente de un gráfico arbitrario, o aproximarlo con una relación de aproximación mejor que 3/2.

También es NP-completo determinar si un gráfico planar tiene un dibujo planar con pendiente número dos, ^[7] y difícil para la teoría existencial de los reales determinar el número de pendiente mínima de un dibujo planar. ^[8]