Skip to Main content Skip to Navigation
Conference papers

Triangle Contact Representations and Duality

Daniel Gonçalves 1 Benjamin Lévêque 1 Alexandre Pinlou 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00620728
Contributor : Benjamin Lévêque <>
Submitted on : Friday, September 18, 2020 - 11:30:17 AM
Last modification on : Tuesday, September 22, 2020 - 9:11:30 AM

File

ark__67375_HCB-ZTN5RGQ8-3.pdf
Publication funded by an institution

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

249

Files downloads

11