Nested triangles graph

More generally, because the nested triangles graphs are planar and 3-vertex-connected, it follows from Steinitz's theorem that they all can be represented as convex polyhedra.

The nested triangles graph was named by Dolev, Leighton & Trickey (1984), who used it to show that drawing an n-vertex planar graph in the integer lattice (with straight line-segment edges) may require a bounding box of size at least n/3 × n/3.

If the outer face is not allowed to be chosen as part of the drawing algorithm, but is specified as part of the input, the same argument shows that a bounding box of size 2n/3 × 2n/3 is necessary, and a drawing with these dimensions exists.

For drawings in which the outer face may be freely chosen, the area lower bound of Dolev, Leighton & Trickey (1984) may not be tight.

When no extra diagonals are added the nested triangles graph itself can be drawn in even smaller area, approximately n/3 × n/2, as shown.