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.
@article{10_37236_7216,
author = {Stefan Felsner and Hendrik Schrezenmaier and Raphael Steiner},
title = {Pentagon contact representations},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {3},
doi = {10.37236/7216},
zbl = {1395.05114},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7216/}
}
TY - JOUR
AU - Stefan Felsner
AU - Hendrik Schrezenmaier
AU - Raphael Steiner
TI - Pentagon contact representations
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/7216/
DO - 10.37236/7216
ID - 10_37236_7216
ER -
%0 Journal Article
%A Stefan Felsner
%A Hendrik Schrezenmaier
%A Raphael Steiner
%T Pentagon contact representations
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/7216/
%R 10.37236/7216
%F 10_37236_7216
Stefan Felsner; Hendrik Schrezenmaier; Raphael Steiner. Pentagon contact representations. The electronic journal of combinatorics, Tome 25 (2018) no. 3. doi: 10.37236/7216
