Triangle Contact Representations and Duality - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2011

Triangle Contact Representations and Duality

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-dual 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-dual 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 node 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.
Fichier principal
Vignette du fichier
ark__67375_HCB-ZTN5RGQ8-3.pdf (220.49 Ko) Télécharger le fichier
Origin : Publication funded by an institution
Loading...

Dates and versions

lirmm-00620728 , version 1 (18-09-2020)

Identifiers

Cite

Daniel Gonçalves, Benjamin Lévêque, Alexandre Pinlou. Triangle Contact Representations and Duality. 18th International Symposium on Graph Drawing (GD), Sep 2010, Konstanz, Germany. pp.262-273, ⟨10.1007/978-3-642-18469-7_24⟩. ⟨lirmm-00620728⟩
135 View
110 Download

Altmetric

Share

Gmail Facebook X LinkedIn More