Triangle Contact Representations and Duality |
| |
Authors: | Daniel Gon?alves Benjamin Lévêque Alexandre Pinlou |
| |
Institution: | 1. LIRMM, CNRS, Universit?? Montpellier 2, 161 rue Ada, 34095, Montpellier Cedex 5, France
|
| |
Abstract: | A?contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. De Fraysseix, Ossona de Mendez and Rosenstiehl proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual. A?primal?Cdual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intersection between the triangles corresponding to u and v is the same point as the intersection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal?Cdual contact representation by triangles. Moreover, the interiors of the triangles form a tiling of the triangle corresponding to the outer face and each contact point is a corner of exactly three triangles. Then we show that these representations are in one-to-one correspondence with generalized Schnyder woods defined by Felsner for 3-connected planar maps. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|