Gráfico de triángulo anidado

Un grafo de triángulos anidados con n vértices es un grafo plano formado por una secuencia de n /3 triángulos cuyos correspondientes pares de vértices están conectados por aristas. También se puede formar geométricamente pegando prismas triangulares a lo largo de sus caras triangulares. Este gráfico y los gráficos estrechamente relacionados se utilizan a menudo en el campo de la visualización de gráficos para demostrar los límites inferiores en el área requerida para varios estilos de dibujo. ${\tfrac{n}{3}}-1$

Representación poliédrica

Un gráfico de triángulo anidado con dos triángulos es un gráfico de prisma triangular , y un gráfico de triángulo anidado con tres triángulos es un gráfico bipiramidal bitruncado . De manera más general, dado que los gráficos de triángulos incrustados son planos y están conectados por 3 vértices , del teorema de Steinitz se deduce que todos pueden representarse como poliedros convexos.

Se puede dar una representación geométrica alternativa de estos gráficos pegando prismas triangulares a lo largo de caras triangulares. El número de triángulos anidados es uno mayor que el número de prismas pegados. Sin embargo, cuando se utilizan prismas rectangulares, el proceso de pegarlos hace que las caras rectangulares adyacentes sean coplanares , por lo que el resultado no es un cuerpo estrictamente convexo.

Límites inferiores del área para dibujos de gráficos

El nombre gráfico de triángulo anidado fue propuesto por Dolev, Layton y Tricky [2] , quienes lo usaron para mostrar que dibujar un gráfico plano con n vértices en una red de enteros (con bordes de segmento de línea ) puede requerir un cuadro delimitador de al menos [3 ] . En tal dibujo, no importa qué cara se elija como borde exterior, se debe dibujar una subsecuencia de al menos n /6 triángulos anidados entre sí, y en esta parte del dibujo cada triángulo debe usar dos filas y dos columnas más, que el siguiente triángulo interior. Si la selección de la cara exterior no está permitida como parte del algoritmo de dibujo, pero se proporciona como parte de la entrada, los mismos argumentos muestran que se necesita un cuadro delimitador de tamaño y que existe un dibujo con esas dimensiones. ${\tfrac {n}{3}}\times {\tfrac {n}{3}}$ ${\tfrac {2n}{3}}\times {\tfrac {2n}{3}}$

Para dibujos en los que la cara exterior se puede elegir libremente, el límite inferior del área de Dolev, Leighton y Tricky [2] puede no ser rígido. Frati y Patrignani [1] demostraron que este gráfico, y cualquier gráfico formado añadiendo diagonales a sus cuadriláteros, se puede dibujar en un rectángulo de tamaño . Si no se agregan diagonales adicionales, el gráfico de triángulo anidado se puede dibujar incluso con un área más pequeña, similar a la figura. Cerrar la brecha entre el límite superior y el límite inferior del área del máximo complemento plano de un gráfico triangular incrustado sigue siendo un problema abierto [4] . ${\tfrac {n}{3}}\times {\tfrac {2n}{3}}$ ${\tfrac {n}{3}}\times {\tfrac {n}{2}}$ ${\tfrac {2n^{2}}{9}}$ ${\tfrac{n^{2}}{9}}$

Problemas sin resolver en matemáticas : ¿Cuál es el área del cuadro delimitador mínimo al dibujar un gráfico triangular anidado en una red, o su terminación plana máxima?

Se han utilizado variantes de gráficos triangulares anidados para muchos otros límites inferiores al dibujar gráficos, como el área de una representación rectangular (cuando los vértices se representan mediante rectángulos y los bordes se dibujan como líneas discontinuas con partes paralelas a los ejes) [5] , el área de dibujos con intersecciones perpendiculares [6] o áreas relativas de una representación plana en comparación con una no plana [7] .

Notas

↑ 12 Frati , Patrignani, 2008 .
↑ 1 2 Dolev, Leighton, Trickey, 1984 .
↑ Dolev, Leighton, Trickey, 1984 , pág. 147–161.
↑ Frati, Patrignani, 2008 , p. 339–344.
↑ Fössmeier, Kant, Kaufmann, 1997 , p. 155–168.
↑ Didimo y Liotta, 2013 , pág. 167–184.
↑ van Kreveld, 2011 , pág. 371–376.

Literatura

Danny Dolev, F. Thomson Leighton, Howard Trickey. Incrustación planar de gráficos planares // Avances en la investigación informática. - 1984. - T. 2 . — S. 147–161 .
Fabrizio Frati, Maurizio Patrignani. Una nota sobre los dibujos de línea recta de área mínima de gráficos planares // Graph Drawing: 15th International Symposium, GD 2007 , Sydney, Australia, 24-26 de septiembre de 2007, Documentos revisados. - Berlín: Springer, 2008. - T. 4875. - S. 339–344. — ( Apuntes de clase en informática ). -doi : 10.1007 / 978-3-540-77537-9_33 .
Ulrich Fössmeier, Goos Kant, Michael Kaufmann. Dibujos de 2 visibilidades de gráficos planos // Dibujo de gráficos: Simposio sobre dibujo de gráficos, GD '96 Berkeley, California, EE. UU., 18 al 20 de septiembre de 1996, Actas. - 1997. - T. 1190. - S. 155-168. — (Apuntes de clase en informática). -doi : 10.1007/ 3-540-62495-3_45 .
Walter Didimo, Giuseppe Liotta. La resolución de los ángulos de cruce en el dibujo de grafos // Treinta ensayos sobre teoría de grafos geométricos / János Pach. - Springer, 2013. - S. 167-184. -doi : 10.1007 / 978-1-4614-0110-0_10 .
Marc van Creveld. La relación de calidad de los dibujos RAC y los dibujos planos de los gráficos planos // Dibujo gráfico: 18º Simposio internacional, GD 2010, Konstanz, Alemania, 21-24 de septiembre de 2010, Documentos seleccionados revisados / Ulrik Brandes, Sabine Cornelsen. - 2011. - T. 6502. - S. 371-376. — (Apuntes de clase en informática). -doi : 10.1007 / 978-3-642-18469-7_34 .