Nested triangles graph

A nested triangles graph with 18 vertices

In graph theory, a nested triangles graph with n vertices is a planar graph 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 prisms on their triangular faces. This graph, and graphs closely related to it, have been frequently used in graph drawing to prove lower bounds on the area requirements of various styles of drawings.

Polyhedral representation

Triangular bifrustum

The nested triangles graph with two triangles is the graph of the triangular prism, and the nested triangles graph with three triangles is the graph of the triangular bifrustum. 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.

An alternative 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

Grid drawing of a nested triangles graph. This layout uses less area than Frati & Patrignani (2008) but unlike theirs does not generalize to maximal planar supergraphs of the nested triangles graph.

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.[1] 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 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. Frati & Patrignani (2008) showed that this graph, and any graph formed by adding diagonals to its quadrilaterals, can be drawn within a box of dimensions n/3 × 2n/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 2n2/9 upper bound and the n2/9 lower bound on drawing area for completions of the nested triangle graph remains an open problem.[2]

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,[3] area of drawings with right angle crossings[4] or relative area of planar versus nonplanar drawings.[5]

References

  1. ↑ Dolev, Danny; Leighton, Tom; Trickey, Howard (1984), "Planar embedding of planar graphs" (PDF), Advances in Computing Research 2: 147–161
  2. ↑ Frati, Fabrizio; Patrignani, Maurizio (2008), "A note on minimum-area straight-line drawings of planar graphs", Graph Drawing: 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007, Revised Papers, Lecture Notes in Computer Science 4875, Berlin: Springer, pp. 339–344, doi:10.1007/978-3-540-77537-9_33, MR 2427831.
  3. ↑ Fößmeier, Ulrich; Kant, Goos; Kaufmann, Michael (1997), "2-visibility drawings of planar graphs", in North, Stephen, Graph Drawing: Symposium on Graph Drawing, GD '96 Berkeley, California, USA, September 18–20, 1996, Proceedings, Lecture Notes in Computer Science 1190, pp. 155–168, doi:10.1007/3-540-62495-3_45.
  4. ↑ Didimo, Walter; Liotta, Giuseppe (2013), "The crossing-angle resolution in graph drawing", in Pach, János, Thirty Essays on Geometric Graph Theory, Springer, pp. 167–184, doi:10.1007/978-1-4614-0110-0_10.
  5. ↑ van Kreveld, Marc (2011), "The quality ratio of RAC drawings and planar drawings of planar graphs", in Brandes, Ulrik; Cornelsen, Sabine, Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers, Lecture Notes in Computer Science 6502, pp. 371–376, doi:10.1007/978-3-642-18469-7_34.
This article is issued from Wikipedia - version of the Monday, August 10, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.