graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a nested triangles graph with ''n'' vertices is a

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

formed from a sequence of ''n''/3 triangles, by connecting pairs of corresponding vertices on consecutive triangles in the sequence. It can also be formed geometrically, by gluing together ''n''/3 − 1

triangular prism In geometry, a triangular prism is a three-sided prism; it is a polyhedron made of a triangular base, a translated copy, and 3 faces joining corresponding sides. A right triangular prism has rectangular sides, otherwise it is ''oblique''. A unif ...

s on their triangular faces. This graph, and graphs closely related to it, have been frequently used in

graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...

to prove lower bounds on the area requirements of various styles of drawings.

Polyhedral representation

The nested triangles graph with two triangles is the graph of the

, and the nested triangles graph with three triangles is the graph of the

triangular bifrustum In geometry, the triangular bifrustum is the second in an infinite series of bifrustum polyhedra. It has 6 trapezoid and 2 triangle faces. It may also be called the truncated triangular bipyramid; however, that term is ambiguous, as it may also r ...

. More generally, because the nested triangles graphs are planar and 3-vertex-connected, it follows from

Steinitz's theorem In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar grap ...

that they all can be represented as convex polyhedra. Another geometric representation of these graphs may be given by gluing triangular prisms end-to-end on their triangular faces; the number of nested triangles is one more than the number of glued prisms. However, using right prisms, this gluing process will cause the rectangular faces of adjacent prisms to be coplanar, so the result will not be strictly convex.

Area lower bounds for graph drawings

The nested triangles graph was named by , who used it to show that drawing an ''n''-vertex planar graph in the

integer lattice In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or grid l ...

(with straight line-segment edges) may require a

bounding box In geometry, the minimum or smallest bounding or enclosing box for a point set in dimensions is the box with the smallest measure (area, volume, or hypervolume in higher dimensions) within which all the points lie. When other kinds of measure a ...

of size at least ''n''/3 × ''n''/3. In such a drawing, no matter which face of the graph is chosen to be the outer face, some subsequence of at least ''n''/6 of the triangles must be drawn nested within each other, and within this part of the drawing each triangle must use two rows and two columns more than the next inner triangle. 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 2''n''/3 × 2''n''/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 may not be tight. showed that this graph, and any graph formed by adding diagonals to its quadrilaterals, can be drawn within a box of dimensions ''n''/3 × 2''n''/3. 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. Closing the gap between the 2''n''²/9 upper bound and the ''n''²/9 lower bound on drawing area for completions of the nested triangle graph remains an open problem. Variants of the nested triangles graph have been used for many other lower bound constructions in graph drawing, for instance on area of rectangular visibility representations, area of drawings with right angle crossings or relative area of planar versus nonplanar drawings..

References

{{reflist Planar graphs Parametric families of graphs