Triangle Contact Representations and Duality

Goncalves, Daniel and Leveque, Benjamin and Pinlou, Alexandre (2011) Triangle Contact Representations and Duality. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 262-273 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_24).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_24
Classifications:Z Theory > Z.250 Geometry
ID Code:1212

Repository Staff Only: item control page

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