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 .
Relación con el grado
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 .
Problema sin resolver en matemáticas :
¿Las gráficas de máximo grado cuatro tienen número de pendiente acotado?
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 4 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]
El método de Keszegh, Pach y Pálvölgyi (2011) para combinar empaquetamientos circulares y árboles cuaternarios para lograr un número de pendiente acotado para gráficos planares con grado acotado
Gráficos planares
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.
Complejidad
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]
Notas
^ Demostrado independientemente por Barát, Matoušek y Wood (2006) y Pach y Pálvölgyi (2006), resolviendo un problema planteado por Dujmović, Suderman y Wood (2005). Véanse los teoremas 5.1 y 5.2 de Pach y Sharir (2009).
^ Mukkamala & Szegedy (2009), mejorando un resultado anterior de Keszegh et al. (2008); teorema 5.3 de Pach y Sharir (2009).
^ Mukkamala y Pálvölgyi (2012).
^ Pach y Sharir (2009).
^ Hansen (1988).
^ Formann y col. (1993); Eades, Hong y Poon (2010); Maňuch et al. (2011).
Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, FT ; Symvonis, A.; Welzl, E. ; Woeginger, G. (1993), "Dibujo de gráficos en el plano con alta resolución", SIAM Journal on Computing , 22 (5): 1035–1052, doi :10.1137/0222063, MR 1237161.
Garg, Ashim; Tamassia, Roberto (2001), "Sobre la complejidad computacional de las pruebas de planaridad ascendente y rectilínea", SIAM Journal on Computing , 31 (2): 601–625, doi :10.1137/S0097539794277123, MR 1861292.
Hansen, Lowell J. (1988), "Sobre el lema del anillo de Rodin y Sullivan", Variables complejas, teoría y aplicación , 10 (1): 23–30, doi :10.1080/17476938808814284, MR 0946096.
Hoffmann, Udo (2016), "El número de pendiente planar", Actas de la 28.ª Conferencia Canadiense sobre Geometría Computacional (CCCG 2016).
Jamison, Robert E. (1984), "Configuraciones planas que determinan pocas pendientes", Geometriae Dedicata , 16 (1): 17–34, doi :10.1007/BF00147419, MR 0757792.
Keszegh, Balázs; Pach, János ; Pálvölgyi, Dömötör; Tóth, Géza (2008), "Dibujo de gráficas cúbicas con como máximo cinco pendientes", Geometría computacional: teoría y aplicaciones , 40 (2): 138–147, doi : 10.1016/j.comgeo.2007.05.003 , MR 2400539.
Malitz, Seth; Papakostas, Achilleas (1994), "Sobre la resolución angular de grafos planos", SIAM Journal on Discrete Mathematics , 7 (2): 172–183, doi :10.1137/S0895480193242931, MR 1271989.
Pach, János ; Pálvölgyi, Dömötör (2006), "Los gráficos de grados acotados pueden tener números de pendiente arbitrariamente grandes", Electronic Journal of Combinatorics , 13 (1): N1, MR 2200545.
Pach, János ; Sharir, Micha (2009), "5.5 Resolución angular y pendientes", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures , Mathematical Surveys and Monographs, vol. 152, American Mathematical Society , págs. 126–127.
Scott, PR (1970), "Sobre los conjuntos de direcciones determinados por n puntos", American Mathematical Monthly , 77 : 502–505, doi :10.2307/2317384, MR 0262933.
Wade, GA; Chu, J.-H. (1994), "Capacidad de dibujo de gráficos completos utilizando un conjunto de pendientes mínimo", The Computer Journal , 37 (2): 139–142, doi : 10.1093/comjnl/37.2.139.
