On Triangle Contact Graphs

Summary

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.

Introduction: on graph drawing

An old problem of geometry consists of representing a simple plane graph G by means of a collection of disks in one-to-one correspondence with the vertices of G. These disks may only intersect pairwise in at most one point, the corresponding contacts representing the edges of G. The case of disks with no prescribed shape is solved by merely drawing for each vertex v a closed curve around v and cutting the edges half way. The difficulty arises when the disks have to be of a specified shape. The famous case of circular disks, solved by the Andreev–Thurston circle packing theorem [1], involves questions of numerical analysis: the coordinates of the centers and radii are not rational, and are computed by means of convergent series. This problem is still up to date, and considered in many research works. In the present paper we will consider triangular disks.