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.
This work was partially supported by the grant ANR-09-JCJC-0041.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Andreev, E.: On convex polyhedra in Lobachevsky spaces. In: Mat. Sbornik, Ser., vol. 81, pp. 445–478 (1970)
Badent, M., Binucci, C., Di Giacomo, E., Didimo, W., Felsner, S., Giordano, F., KratochvÃI, J. Palladino, P., Patrignani, M., Trotta., F.: Homothetic triangle contact representations of planar graphs. In: Proceedings of the 19th Canadian Conference on Computational Geometry CCCG 2007, pp. 233–236 (2007)
Bonichon, N., Felsner, S., Mosbah, M.: Convex Drawings of 3-Connected Plane Graphs. Algorithmica 47, 399–420 (2007)
Felsner, S.: Convex Drawings of Planar Graphs and the Order Dimension of 3-Polytopes. Order 18, 19–37 (2001)
Felsner, S.: Geodesic Embeddings and Planar Graphs. Order 20, 135–150 (2003)
Felsner, S.: Lattice structures from planar graphs. Electron. J. Combin. 11 (2004)
Felsner, S., Zickfeld, F.: Schnyder Woods and Orthogonal Surfaces. Discrete Comput. Geom. 40, 103–126 (2008)
de Fraysseix, H., Ossona de Mendez, P., Rosenstiehl, P.: On Triangle Contact Graphs. Combinatorics, Probability and Computing 3, 233–246 (1994)
de Fraysseix, H., Ossona de Mendez, P.: On topological aspects of orientations. Discrete Mathematics 229, 57–72 (2001)
de Fraysseix, H., de Mendez, P.O.: Barycentric systems and stretchability. Discrete Applied Mathematics 155, 1079–1095 (2007)
Gansner, E.R., Hu, Y., Kaufmann, M., Kobourov, S.G.: Optimal Polygonal Representation of Planar Graphs. In: López-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 417–432. Springer, Heidelberg (2010)
Gansner, E.R., Hu, Y., Kobourov, S.G.: On Touching Triangle Graphs. In: Proc. Graph Drawing (2010), http://arxiv1.library.cornell.edu/abs/1001.2862v1
Kaufmann, M., Kratochvíl, J., Lehmann, K.A., Subramanian, A.R.: Max-tolerance graphs as intersection graphs: Cliques, cycles and recognition. In: Proc. SODA 2006, pp. 832–841 (2006)
Koebe, P.: Kontaktprobleme der konformen Abbildung. Berichte Äuber die Verhandlungen d. SÄachs. Akad. d. Wiss., Math.-Phys. Klasse 88, 141–164 (1936)
Kratochvíl, J.: Bertinoro Workshop on Graph Drawing (2007)
Miller, E.: Planar graphs as minimal resolutions of trivariate monomial ideals. Documenta Mathematica 7, 43–90 (2002)
Schnyder, W.: Planar graphs and poset dimension. Order 5, 323–343 (1989)
Schramm, O.: Combinatorically Prescribed Packings and Applications to Conformal and Quasiconformal Maps, Modified version of PhD thesis from (1990), http://arxiv.org/abs/0709.0710v1
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gonçalves, D., Lévêque, B., Pinlou, A. (2011). Triangle Contact Representations and Duality. In: Brandes, U., Cornelsen, S. (eds) Graph Drawing. GD 2010. Lecture Notes in Computer Science, vol 6502. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18469-7_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-18469-7_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-18468-0
Online ISBN: 978-3-642-18469-7
eBook Packages: Computer ScienceComputer Science (R0)