SFU Discrete Math Seminar: Stephen Kobourov
- Date: 02/15/2023
- Time: 11:30
Simon Fraser University
Contact Representation of Planar Graphs in 2D and 3D
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.
Location: SFU - SCK 9509
Time: 11.30am Pacific