En el dibujo de gráficos y la teoría de grafos geométricos , el número de pendiente de un gráfico es el número mínimo posible de pendientes distintas de aristas en un dibujo de la gráfica en la que los vértices se representan como puntos en el plano euclidiano y las aristas como segmentos de línea que lo hacen. no pasar por ningún vértice no incidente.
Gráficos completos
Aunque anteriormente se habían estudiado problemas estrechamente relacionados en geometría discreta , por ejemplo, por Scott (1970) y Jamison (1984) , el problema de determinar el número de pendiente de una gráfica fue introducido por Wade y Chu (1994) , quienes demostraron que el número de pendiente de un gráfico completo de n - vértices, K n es exactamente n . Se puede formar un dibujo con este número de pendiente colocando los vértices del gráfico en un polígono regular .
Relación con el grado
El número de pendiente de una gráfica de grado máximo d es claramente al menos, porque como máximo dos de los bordes 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 gráfico, ya que los bordes de una sola pendiente deben formar un bosque lineal , y la arboricidad lineal a su vez es al menos.
¿Tienen las gráficas de grado máximo cuatro un número de pendiente acotado?
Existen gráficos con un grado máximo de cinco que tienen un número de pendiente arbitrariamente grande. [1] Sin embargo, cada gráfico 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 gráfico completo K 4 muestra que esto es ajustado. No todos los conjuntos de cuatro pendientes son adecuados para dibujar todos los gráficos de grado 3: un conjunto de pendientes es adecuado para este propósito si y solo forma las pendientes de los lados y diagonales de un paralelogramo . En particular, se puede dibujar cualquier gráfico de grado 3 de modo que sus bordes sean paralelos al eje o paralelos a las diagonales principales de la red de números enteros . [3] No se sabe si las gráficas de grado máximo cuatro tienen un número de pendiente acotado o ilimitado. [4]
Gráficos planos
Como demostraron Keszegh, Pach & Pálvölgyi (2011) , cada gráfico plano tiene un dibujo de línea recta en el que el número de pendientes distintas es función del grado del gráfico. Su demostración sigue una construcción de Malitz y Papakostas (1994) para delimitar la resolución angular de gráficos planos como una función de grado, completando el gráfico a un gráfico plano máximo sin aumentar su grado en más de un factor constante, y aplicando el círculo teorema de empaquetamiento para representar este gráfico aumentado como una colección de círculos tangentes. Si el grado del gráfico inicial está acotado, la razón entre los radios de los círculos adyacentes en el empaque 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 gráfico en un punto dentro de su círculo producirá pendientes que son proporciones de números enteros pequeños. El número de pendientes distintas producidas por esta construcción es exponencial en el grado del gráfico.
Complejidad
Es NP-completo determinar si una gráfica 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 plano tiene un dibujo plano con pendiente número dos, [7] y difícil para la teoría existencial de los reales determinar el número de pendiente mínimo de un dibujo plano. [8]
Notas
- ^ Probado de forma independiente por Barát, Matoušek & Wood (2006) y Pach & Pálvölgyi (2006) , resolviendo un problema planteado por Dujmović, Suderman & Wood (2005) . Ver teoremas 5.1 y 5.2 de Pach & Sharir (2009) .
- ^ Mukkamala & Szegedy (2009) , mejorando un resultado anterior de Keszegh et al. (2008) ; teorema 5.3 de Pach & 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 y col. (2011) .
- ^ Garg y Tamassia (2001) .
- ^ Hoffmann (2016) .
Referencias
- Barát, János; Matoušek, Jiří ; Wood, David R. (2006), "Los gráficos de grados acotados tienen un grosor geométrico arbitrariamente grande" , Electronic Journal of Combinatorics , 13 (1): R3, MR 2200531.
- Dujmović, Vida; Suderman, Matthew; Wood, David R. (2005), "Really straight graph drawings", en Pach, János (ed.), Graph Drawing: 12th International Symposium, GD 2004, Nueva York, NY, EE. UU., 29 de septiembre al 2 de octubre de 2004, Artículos seleccionados revisados , Lecture Notes in Computer Science , 3383 , Berlín: Springer-Verlag, págs. 122-132, arXiv : cs / 0405112 , doi : 10.1007 / 978-3-540-31843-9_14.
- Eades, Peter ; Hong, Seok-Hee; Poon, Sheung-Hung (2010), "Sobre el dibujo rectilíneo de gráficos", en Eppstein, David ; Gansner, Emden R. (eds.), Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, EE. UU., 22-25 de septiembre de 2009, Revised Papers , Lecture Notes in Computer Science, 5849 , Berlín: Springer, págs. 232–243, doi : 10.1007 / 978-3-642-11805-0_23 , MR 2680455.
- Formann, M .; Hagerup, T .; Haralambides, J .; Kaufmann, M .; Leighton, FT ; Symvonis, A .; Welzl, E .; Woeginger, G. (1993), "Dibujar 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 plana", 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 (2011), "Dibujar gráficas planas de grado acotado con pocas pendientes", en Brandes, Ulrik; Cornelsen, Sabine (eds.), Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Alemania, 21-24 de septiembre de 2010, Revised Selected Papers , Lecture Notes in Computer Science, 6502 , Heidelberg: Springer, págs. 293–304 , arXiv : 1009.1315 , doi : 10.1007 / 978-3-642-18469-7_27 , MR 2781274.
- Keszegh, Balázs; Pach, János ; Pálvölgyi, Dömötör; Tóth, Géza (2008), "Dibujar gráficas cúbicas con un máximo de 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 gráficos planos", SIAM Journal on Discrete Mathematics , 7 (2): 172-183, doi : 10.1137 / S0895480193242931 , MR 1271989.
- Maňuch, Ján; Patterson, Murray; Poon, Sheung-Hung; Thachuk, Chris (2011), "Complejidad de encontrar dibujos rectilíneos no planos de gráficos", en Brandes, Ulrik; Cornelsen, Sabine (eds.), Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Alemania, 21-24 de septiembre de 2010, Revised Selected Papers , Lecture Notes in Computer Science, 6502 , Heidelberg: Springer, págs. 305–316 , doi : 10.1007 / 978-3-642-18469-7_28 , HDL : 10281/217381 , MR 2781275.
- Mukkamala, Padmini; Szegedy, Mario (2009), "Representación geométrica de grafos cúbicos con cuatro direcciones", Geometría computacional: teoría y aplicaciones , 42 (9): 842–851, doi : 10.1016 / j.comgeo.2009.01.005 , MR 2543806.
- Mukkamala, Padmini; Pálvölgyi, Dömötör (2012), "Dibujar gráficas cúbicas con las cuatro pendientes básicas", en van Kreveld, Marc; Speckmann, Bettina (eds.), Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, Países Bajos, 21-23 de septiembre de 2011, Revised Selected Papers , Lecture Notes in Computer Science, 7034 , Springer, págs. 254–265, arXiv : 1106.1973 , doi : 10.1007 / 978-3-642-25878-7_25.
- 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", Geometría combinatoria y sus aplicaciones algorítmicas: Las conferencias de Alcalá , Encuestas y monografías matemáticas, 152 , American Mathematical Society , pp. 126-127.
- Scott, PR (1970), "Sobre los conjuntos de direcciones determinadas por n puntos", American Mathematical Monthly , 77 : 502–505, doi : 10.2307 / 2317384 , MR 0262933.
- Wade, GA; Chu, J.-H. (1994), "Dibujabilidad de gráficos completos usando un conjunto de pendiente mínima", The Computer Journal , 37 (2): 139-142, doi : 10.1093 / comjnl / 37.2.139.