Gráfico de triángulos anidados
En teoría de grafos , un gráfico de triángulos anidados con n vértices es un gráfico plano formado a partir de una secuencia de n /3 triángulos, conectando pares de vértices correspondientes en triángulos consecutivos en la secuencia. También se puede formar geométricamente, pegando n /3 − 1 prismas triangulares en sus caras triangulares. Este gráfico, y los gráficos estrechamente relacionados con él, se han utilizado con frecuencia en el dibujo de gráficos para demostrar los límites inferiores de los requisitos de área de varios estilos de dibujos.
El gráfico de triángulos anidados con dos triángulos es el gráfico del prisma triangular , y el gráfico de triángulos anidados con tres triángulos es el gráfico del bifrustum triangular . De manera más general, debido a que los gráficos de triángulos anidados 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 de extremo a extremo en sus caras triangulares; el número de triángulos anidados es uno más que el número de prismas pegados. Sin embargo, utilizando prismas rectos, este proceso de pegado hará que las caras rectangulares de los prismas adyacentes sean coplanares, por lo que el resultado no será estrictamente convexo.
El gráfico de triángulos anidados fue nombrado por Dolev, Leighton & Trickey (1984) , quienes lo usaron para mostrar que dibujar un gráfico plano de n vértices en la red de enteros (con bordes de segmento de línea recta ) puede requerir un cuadro delimitador de tamaño al menos n /3 × n /3. [1] En tal dibujo, sin importar qué cara del gráfico se elija como la cara exterior, alguna subsecuencia de al menos n/6 de los triángulos deben dibujarse anidados entre sí, y dentro de esta parte del dibujo, cada triángulo debe usar dos filas y dos columnas más que el siguiente triángulo interior. Si no se permite elegir la cara exterior como parte del algoritmo de dibujo, pero se especifica como parte de la entrada, el mismo argumento muestra que es necesario un cuadro delimitador de tamaño 2 n /3 × 2 n /3, y un dibujo con estas dimensiones existe.
Para dibujos en los que la cara exterior puede elegirse libremente, el límite inferior del área de Dolev, Leighton & Trickey (1984) puede no ser estricto. Frati & Patrignani (2008) demostraron que este gráfico, y cualquier gráfico formado al sumar diagonales a sus cuadriláteros, se pueden dibujar dentro de una caja de dimensiones n /3 × 2 n /3. Cuando no se agregan diagonales adicionales, el gráfico de triángulos anidados se puede dibujar en un área aún más pequeña, aproximadamente n /3 × n /2, como se muestra. Cerrar la brecha entre el límite superior de 2 n 2/9 y el límite inferior de n 2/9 en el área de dibujo para completar el gráfico de triángulo anidado sigue siendo un problema abierto. [2]
¿Cuál es el área mínima del cuadro delimitador de un dibujo de cuadrícula del gráfico de triángulos anidados, o de sus completaciones planas máximas?
