
arXiv: 2004.05942
Representations of planar triangulations as contact graphs of a set of internally disjoint homothetic triangles or of a set of internally disjoint homothetic squares have received quite some attention in recent years. 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, respectively. In particular there is a bijection to certain $\alpha$-orientations and consequently a lattice structure on the set of five color forests of a given graph. This lattice structure plays a role in an algorithm that is supposed to compute a contact representation with pentagons for a given graph. Based on a five color forest the algorithm builds a system of linear equations and solves it, if the solution is non-negative, it encodes distances between corners of a pentagon representation. In this case the representation is constructed and the algorithm terminates. Otherwise negative variables guide a change of the five color forest and the procedure is restarted with the new five color forest. Similar algorithms have been proposed for contact representations with homothetic triangles and with squares.
Computational Geometry (cs.CG), FOS: Computer and information sciences, planar triangulation, Graph representations (geometric and intersection representations, etc.), pentagon, contact representation, 05C62, 68R10, Graph algorithms (graph-theoretic aspects), FOS: Mathematics, Computer Science - Computational Geometry, Mathematics - Combinatorics, Analysis of algorithms, Combinatorics (math.CO), Schnyder wood
Computational Geometry (cs.CG), FOS: Computer and information sciences, planar triangulation, Graph representations (geometric and intersection representations, etc.), pentagon, contact representation, 05C62, 68R10, Graph algorithms (graph-theoretic aspects), FOS: Mathematics, Computer Science - Computational Geometry, Mathematics - Combinatorics, Analysis of algorithms, Combinatorics (math.CO), Schnyder wood
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
