BARC talk by prof. Stephen Kobourov, University of Arizona

Abstract:

In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. We show how to use Schnyder realizers and canonical orders for planar graphs to obtain different types of contact representations.

Specifically, we describe an algorithm that constructs proportional contact representation for arbitrary planar graphs using 10-sided rectilinear polygons. We also describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity, as 8-sided polygons are sometimes necessary. In 3D vertices are represented by polytopes and edges by contacts between the corresponding polytopes contacts. We show that planar 3-trees have contact representations with cubes and proportional contact representations with boxes.