Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-06T01:21:32.841Z Has data issue: false hasContentIssue false
  • English
  • Français

On Triangle Contact Graphs†

Published online by Cambridge University Press:  12 September 2008

Hubert de Fraysseix ,
Patrice Ossona de Mendez  and
Pierre Rosenstiehl
Hubert de Fraysseix
Affiliation:
CNRS, EHESS, 54 Boulevard Raspail, 75006, Paris, France
Patrice Ossona de Mendez
Affiliation:
CNRS, EHESS, 54 Boulevard Raspail, 75006, Paris, France
Pierre Rosenstiehl
Affiliation:
CNRS, EHESS, 54 Boulevard Raspail, 75006, Paris, France
Get access Rights & Permissions [Opens in a new window]

Abstract

It is proved that any plane graph may be represented by a triangle contact system, that is a collection of triangular disks which are disjoint except at contact points, each contact point being a node of exactly one triangle. Representations using contacts of T-or Y-shaped objects follow. Moreover, there is a one-to-one mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 2 , June 1994 , pp. 233 - 246
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Andreev, E. M. (1970) On convex polyhedra in Lobacevskii spaces. Mat. Sb. 81 445–478.Google Scholar
[2]Di Battista, G., Eades, P., Tamassia, R. and Tollis, I. G. (1989) Algorithms for drawing planar graphs: an annotated bibliography. Tech. Rep. No. CS-89–09, Brown University, 1989.Google Scholar
[3]de Fraysseix, H. and de Mendez, P. O. (In preparation) On tree decompositions and angle marking of planar graphs.Google Scholar
[4]de Fraysseix, H., de Mendez, P. O. and Pach, J. (submitted) A streamlined depth-first search algorithm revisited.Google Scholar
[5]de Fraysseix, H., de Mendez, P. O. and Pach, J. (1993) Representation of planar graphs by segments. Intuitive Geometry (to appear).Google Scholar
[6]de Fraysseix, H., Pach, J. and Pollack, R. (1990) Small sets supporting Fary embeddings of planar graphs. Combinatorica 10 41–51.Google Scholar
[7]Mohar, B. (To appear) Circle packings of maps in polynomial time.Google Scholar
[8]Rosenstiehl, P., and Tarjan, R. E. (1986) Rectilinear planar layout and bipolar orientation of planar graphs. Discrete and Computational Geometry 1 343–353.CrossRefGoogle Scholar
[9]Schnyder, W. (1990) Embedding planar graphs on the grid. In: Proc. ACM-SIAM Symp. on Discrete Algorithms 138–148.Google Scholar
[10]Tamassia, R. and Tollis, I. G. (1989) Tessellation representation of planar graphs. In: Proc. Twenty-Seventh Annual Allerton Conference on Communication, Control, and Computing48–57.Google Scholar