کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777103 | 1632570 | 2017 | 7 صفحه PDF | دانلود رایگان |

Representations of planar triangulations as contact graphs of geometric shapes have received quite some attention in recent years. The most prominent example is Koebe's 'kissing coins theorem', but representations with internally disjoint homothetic triangles or squares have also been studied. In this paper we investigate representations of planar triangulations as contact graphs of a set of internally disjoint homothetic pentagons. Surprisingly, such a representation exists for every triangulation whose outer face is a 5-gon. We relate these representations to five color forests. These combinatorial structures resemble Schnyder woods and transversal structures. In particular there is a bijection to certain α-orientations and consequently a lattice structure on the set of five color forests of a given graph. This distributive lattice plays a role in a heuristic that is supposed to compute a contact representation with pentagons for a given graph.
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 421-427