Gráfico de triángulos anidados

En teoría de grafos , un grafo de triángulos anidados con n vértices es un grafo planar formado a partir de una secuencia de n /3 triángulos, conectando pares de vértices correspondientes en triángulos consecutivos de la secuencia. También puede formarse geométricamente, uniendo n /3  −  1 prismas triangulares por sus caras triangulares. Este grafo, y otros grafos estrechamente relacionados, se han utilizado con frecuencia en el dibujo de grafos para demostrar límites inferiores en los requisitos de área de diversos estilos de dibujo.

El grafo de triángulos anidados con dos triángulos es el grafo del prisma triangular , y el grafo de triángulos anidados con tres triángulos es el grafo del bifrustum triangular . En términos más generales, dado que los grafos de triángulos anidados son planos y conexos por 3 vértices , se deduce del teorema de Steinitz que todos ellos pueden representarse como poliedros convexos.

Otra representación geométrica de estos gráficos se puede obtener pegando prismas triangulares extremo con extremo por sus caras triangulares; el número de triángulos anidados es uno más que el número de prismas pegados. Sin embargo, al usar 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 grafo de triángulos anidados fue nombrado por Dolev, Leighton y Trickey (1984) , quienes lo utilizaron para demostrar que dibujar un grafo planar de n vértices en la red entera (con aristas de segmentos de línea recta ) puede requerir una caja delimitadora de tamaño al menos n /3  × n /3. ^{[ 1 ]} En dicho dibujo, independientemente de qué cara del grafo se elija como cara exterior, alguna subsecuencia de al menos n /6 de los triángulos debe dibujarse anidada una dentro de la otra, 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 necesaria una caja delimitadora de tamaño 2n / 3 × 2n / 3, y existe un dibujo con estas dimensiones.   

Para dibujos en los que la cara exterior puede elegirse libremente, el límite inferior del área de Dolev, Leighton y Trickey (1984) puede no ser ajustado. Frati y Patrignani (2008) demostraron que este grafo, y cualquier grafo formado al añadir diagonales a sus cuadriláteros, puede dibujarse dentro de una caja de dimensiones n /3  ×  2n / 3. Cuando no se añaden diagonales adicionales, el propio grafo de triángulos anidados puede dibujarse en un área aún menor, aproximadamente ⁿ / 3  × n /2, como se muestra. Cerrar la brecha entre el límite superior 2n² /9 y el límite inferior n² ^/ 9 del área de dibujo para completaciones del grafo de triángulos anidados sigue siendo un problema abierto. ^{[ 2 ]} 

Se han utilizado variantes del gráfico de triángulos anidados para muchas otras construcciones de límites inferiores en el dibujo de gráficos, por ejemplo, en el área de representaciones de visibilidad rectangular, ^{[ 3 ]} el área de dibujos con cruces en ángulo recto ^{[ 4 ]} o el área relativa de dibujos planos frente a no planos. ^{[ 5 ]}