论文标题
五角大楼的接触表示
Pentagon contact representations
论文作者
论文摘要
近年来，平面三角剖分作为一组内部不相交的三角形或一组内部不相交的同性恋平方的触点图已引起了很多关注。在本文中，我们研究了平面三角剖分的表示形式，作为一组内部不相交的pentagons的接触图。令人惊讶的是，每个三角剖分都是5 gon的三角剖分。我们将这些代表与五种彩色森林联系起来。这些组合结构分别类似于Schnyder木材和横向结构。特别是对某些α-取向有两者的态度，因此在给定图的五个彩色森林集上是一个晶格结构。该晶格结构在算法中起作用，该算法应计算给定图的Pentagons的触点表示。基于五彩色森林，算法构建了线性方程系统并解决该系统，如果解决方案是非负的，则它会编码五角大楼表示的角落之间的距离。在这种情况下，构建表示形式并终止算法。否则，负变量指导五种颜色森林的变化，并且该过程与新的五种彩色森林重新启动。已经提出了类似的算法，用于与同型三角形和正方形的接触表示。
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.
